#include #include using namespace std; const int MAX=210000; const long long MOD=100000000000000000; typedef long long ll; ll fac[MAX],finv[MAX],inv[MAX]; ll mod_pow(ll x, ll n){ //べき乗 ll ans=1; while(n!=0){ if(n&1) ans=ans*x%MOD; x=x*x%MOD; n=n>>1; } return ans; } void com_init(){ //初期化 fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i> s; int imos[s.size()]; for(int i=0;i