#include using namespace std; #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) using ll = long long; using P = std::tuple; const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1}; int Gx, Gy, K; ll Xs[100], Ys[100], Cs[100]; namespace tottori{ // until C++17 template constexpr size_t size(const T (&array)[N]){ return N; } }; template T expt(T a, T n, T mod = std::numeric_limits::max()){ T res = 1; while(n){ if(n & 1){res = res * a % mod;} a = a * a % mod; n >>= 1; } return res; } template T inverse(T n, T mod){ return expt(n, mod-2, mod); } ll fact[410], inv[410]; // nCk template T nCk(T n, T k, T mod = std::numeric_limits::max()){ if(n < k){return 0;} return fact[n] * inv[k] % mod * inv[n-k] % mod; } void initFactAndInv(ll mod){ fact[0] = 1; inv[0] = 1; for(int i=1;i> Gx >> Gy >> K; for(int i=0;i> Xs[i] >> Ys[i] >> Cs[i]; } ll res = 0ll; for(int i=0;i<=Cs[0];++i){ for(int j=0;j<=Cs[1];++j){ for(int k=0;k<=Cs[2];++k){ for(int l=0;l<=Cs[3];++l){ for(int m=0;m<=Cs[4];++m){ ll cs[5] = {i, j, k, l, m}; ll x = 0ll, y = 0ll; for(int a=0;a<5;++a){ x += 1ll * Xs[a] * cs[a]; y += 1ll * Ys[a] * cs[a]; } // std::cout << x << " " << y << std::endl; ll z = 1ll; int sum = i + j + k + l + m, pr = 0; for(int a=0;a<5;++a){ // std::cout << (sum - pr) << " " << cs[a] << std::endl; z = z * nCk(1ll * sum - pr, cs[a], 1000000007ll) % 1000000007ll; pr += cs[a]; } if(x == Gx && y == Gy){ res = (res + z) % 1000000007ll; } } } } } } std::cout << res << std::endl; }