#include #include #define INF 1000000000LL using namespace std; typedef long long ll; typedef pair P; std::random_device rd; ll mod_pow(ll x,ll n,ll mod){ ll res=1; while(n>0){ if(n&1LL)res=res*x%mod; x=x*x%mod; n>>=1; } return res; } ll calc(ll v,ll tgt,int po){ ll ans=1; for(int i=0;itgt)return false; } if(anstgt)return false; return true; } bool is_prime(ll val){ if(val==1LL)return false; if(val==2LL)return true; for(int i=0;i<10;i++){ ll v=0; v=rd()%val; if(v==0LL)v=1; if(mod_pow(v,val-1LL,val)!=1LL)return false; } return true; } bool C(ll v,ll tgt,int po){ ll res=1; for(int i=0;i