Pagini recente » Cod sursa (job #190927) | Cod sursa (job #796112) | Cod sursa (job #1777382) | Cod sursa (job #3251133) | Cod sursa (job #3233564)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
// Function to calculate the number of valid matrices
long long countValidMatrices(int N) {
vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= N; ++i) {
dp[i][0] = dp[i - 1][0] * 2 % MOD;
}
for (int j = 1; j <= N; ++j) {
dp[0][j] = dp[0][j - 1] * 2 % MOD;
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
dp[i][j] = dp[i][j] * 2 % MOD;
}
}
return dp[N][N];
}
int main() {
ifstream infile("patrate2.in");
ofstream outfile("patrate2.out");
int N;
infile >> N;
long long result = countValidMatrices(N);
outfile << result << endl;
infile.close();
outfile.close();
return 0;
}