#include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) typedef long long ll; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define INF 2140000000 const long long MOD = 1000000007; using namespace std; const int max_comb=300000; vector fac(max_comb+1); //n! (mod M) vector ifac(max_comb+1); //k!^(-1) (mod M) ll mpow(ll x, ll n){ //x^n(mod M) ll ans = 1; while(n != 0){ if(n&1) ans = ans*x % MOD; x = x*x % MOD; n = n >> 1; } return ans; } ll minv(ll x){ return mpow( x, MOD-2 ); } ll comb(int a, int b){ // C(a,b) = a! * b!^(-1) * (a-b)^(-1) if(a == 0 && b == 0)return 1; if(a < b || a < 0)return 0; ll tmp = ifac[a-b]* ifac[b] % MOD; return tmp * fac[a] % MOD; } ll perm(int a, int b){ // P(a,b) = a! * (a-b)!^(-1) if(b == 0)return 1; if(a < b || a < 0)return 0; ll tmp = ifac[a-b] % MOD; return tmp * fac[a] % MOD; } void pre_comb() { fac[0] = 1; ifac[0] = 1; for(int i = 0; i x(a+b+c); int i; x[0]=1; for(i=1; i=b+c? comb(i-c,b): 0) +MOD)%MOD) %MOD; sum = (sum+val)%MOD; } printf("%lld\n", sum); return 0; }