Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int maxN = 1e3 + 9;
- const int maxM = 1e3 + 9;
- const int MOD = 1e9 + 7;
- long long memo[maxN][maxM], N, M;
- long long nCr[maxN][maxN];
- long long dp (int row, int lastRowOnes) {
- if (row == N + 1)
- return 1;
- if (memo[row][lastRowOnes] != -1)
- return memo[row][lastRowOnes];
- long long res = 0;
- for (int powerOf2 = 2; powerOf2 <= 2 * M; powerOf2 *= 2) {
- int thisRowSum = powerOf2 - lastRowOnes;
- if (thisRowSum <= M && thisRowSum >= 0) {
- res += nCr[M][thisRowSum] * dp (row + 1, thisRowSum) % MOD;
- res %= MOD;
- }
- }
- return memo[row][lastRowOnes] = res;
- }
- int main() {
- cin >> N >> M;
- nCr[0][0] = 1;
- for (int i = 1; i <= M; i++) {
- nCr[i][0] = nCr[i][i] = 1;
- for (int j = 1; j < i; j++) {
- nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % MOD;
- }
- }
- memset (memo, -1, sizeof (memo));
- long long res = 0;
- for (int i = 0; i <= M; i++) {
- res += dp (2, i) * nCr[M][i] % MOD;
- res %= MOD;
- }
- cout << res << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement