#include <stdio.h>
#define N 300
#define M 300
#define A 300
#define MD 1000000007
int vv[N + M], ff[N + M], gg[N + M];
void init() {
int i;
ff[0] = gg[0] = 1;
for (i = 1; i < N + M; i++) {
vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
ff[i] = (long long) ff[i - 1] * i % MD;
gg[i] = (long long) gg[i - 1] * vv[i] % MD;
}
}
int choose(int n, int k) {
return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}
int main() {
static int aa[N][M], dp[N][M][A];
int n, m, c, i, j, a, b, ans;
init();
scanf("%d%d%d", &n, &m, &c);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &aa[i][j]);
dp[0][0][aa[0][0]] = 1;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
if (i == 0 && j == 0)
continue;
a = aa[i][j];
for (b = a; b < c; b += a)
dp[i][j][b] = ((i == 0 ? 0 : dp[i - 1][j][b / aa[i][j]]) + (j == 0 ? 0 : dp[i][j - 1][b / aa[i][j]])) % MD;
}
ans = 0;
for (b = 1; b < c; b++)
ans = (ans + dp[n - 1][m - 1][b]) % MD;
ans = (choose(n - 1 + m - 1, n - 1) - ans + MD) % MD;
printf("%d\n", ans);
return 0;
}
Compilation message
mobitel.c: In function 'main':
mobitel.c:30:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%d%d%d", &n, &m, &c);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
mobitel.c:33:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d", &aa[i][j]);
| ^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
192 ms |
65540 KB |
Execution killed with signal 9 |
| 3 |
Execution timed out |
6064 ms |
5564 KB |
Time limit exceeded |
| 4 |
Execution timed out |
6076 ms |
5912 KB |
Time limit exceeded |
| 5 |
Execution timed out |
6056 ms |
6316 KB |
Time limit exceeded |
| 6 |
Execution timed out |
6059 ms |
6224 KB |
Time limit exceeded |
| 7 |
Execution timed out |
6034 ms |
6512 KB |
Time limit exceeded |
| 8 |
Execution timed out |
6049 ms |
5456 KB |
Time limit exceeded |
| 9 |
Execution timed out |
6071 ms |
5404 KB |
Time limit exceeded |
| 10 |
Execution timed out |
6036 ms |
5660 KB |
Time limit exceeded |
