codeforce 258#E(lucas+容斥+組合）

codeforce 258#E(lucas+容斥+組合）

CF 451E

#include
#include
#include

using namespace std;

typedef long long ll;
const ll mod=1000000007;


ll qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }

    return ans;
}

ll C(ll m,ll n,ll p)
{
    if(n>m) return 0;
    if(m-na^(p-2)=a^-1(mod p)->a^(p-2)是a mod p的逆；
cm(a,b)%p==a! / (b!*(a-b)!) mod p==a! * (b!*(a-b)!)^(p-2) mod p
也= (a!/(a-b)!) * (b!)^(p-2)) mod p
這裡，其實就是直接求 (a!/(a-b)!) / (b!) mod p
由於 (a/b) mod p = a * b^(p-2) mod p
*/

int n;
ll s,f[25];

ll solve()
{
    ll ans=0;
    for(int i=0;i<(1<