#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; // a,b の最大公約数と、ax + by = gcd(a,b) となる x,y を求める long long extgcd(long long a, long long b, long long &x, long long &y) { long long g = a; if(b != 0){ g = extgcd(b, a % b, y, x); y -= (a / b) * x; }else{ x = 1; y = 0; } return g; } // ax ≡ gcd(a, m) (mod m) となる x を求める // a, m が互いに素ならば、関数値は mod m での a の逆数となる long long mod_inverse(long long a, long long m) { long long x, y; extgcd(a, m, x, y); return (x % m + m) % m; } // 階乗数の事前計算を用いた各種組合せ class FactorialCalculation { private: const int mod; vector factorial; vector invFactorial; public: FactorialCalculation(int n, int mod) : mod(mod) { factorial.resize(n+1, 1); invFactorial.resize(n+1, 1); for(int i=1; i<=n; ++i){ factorial[i] = factorial[i-1] * i % mod; invFactorial[i] = mod_inverse(factorial[i], mod); } } long long getFactorial(int n){ return factorial[n]; } long long getPermutation(int n, int r){ if(n < r) return 0; return factorial[n] * invFactorial[n-r] % mod; } long long getCombination(int n, int r){ if(n < r) return 0; return getPermutation(n, r) * invFactorial[r] % mod; } long long getHomogeneous(int n, int r){ return getCombination(n+r-1, r); } }; const int MOD = 1000000007; int w, h, n; vector dx, dy, m; FactorialCalculation calc(75, MOD); long long solve(int i, int y, int x, int cnt, long long tmp) { if(i == n){ if(y == h && x == w) return tmp; else return 0; } long long ans = 0; for(int j=0; j<=m[i]; ++j){ int y2 = y + dy[i] * j; int x2 = x + dx[i] * j; long long tmp2 = tmp * calc.getCombination(cnt+j, j) % MOD; ans += solve(i+1, y2, x2, cnt + j, tmp2); ans %= MOD; } return ans; } int main() { cin >> w >> h >> n; dx.resize(n); dy.resize(n); m.resize(n); for(int i=0; i> dx[i] >> dy[i] >> m[i]; cout << solve(0, 0, 0, 0, 1) << endl; return 0; }