1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll qpow(ll x, int n) {
ll ret = 1;
while (n) {
if (n & 1) ret = ret * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return ret;
}
int n, l, m;
int q[2005], t[2005], s[2005];
ll sum_q = 0;
ll inv_sum_q = 0;
ll p[2005];
ll f[2005];
ll ans = 0;
int main() {
scanf("%d%d%d", &n, &l, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &q[i], &t[i], &s[i]);
sum_q += q[i];
}
inv_sum_q = qpow(sum_q, MOD - 2);
for (int i = 1; i <= m; ++i)
p[i] = 1ll * q[i] * inv_sum_q % MOD;
f[0] = 0;
for (int i = 1; i <= l; ++i) {
for (int j = 1; j <= m; ++j) {
if (i - t[j] < 0) continue;
if (i - t[j] == 0) {
if (s[j] == 0)
f[i] = (f[i] + p[j]) % MOD;
continue;
}
f[i] = (f[i] + p[j] * qpow(f[i - t[j]], s[j]) % MOD) % MOD;
}
}
ans = qpow(f[l], n);
ans = (1ll - ans + MOD) % MOD;
printf("%lld\n", ans);
return 0;
}
|