#include using namespace std; using ll=long long; #define int ll #define FOR(i,a,b) for(int i=int(a);i; using vi=vector; using ld=long double; template ostream& operator<<(ostream& os,const pair& p){ os<<"("< ostream& operator <<(ostream& os,const vector& v){ os<<"["; REP(i,(int)v.size()){ if(i)os<<","; os< void chmax(T& a,U b){ if(a void chmin(T& a,U b){ if(a>b) a=b; } template T Sq(const T& t){ return t*t; } const int inf=LLONG_MAX/3; const int mod=1000000007; template void add(T& a,U b){ a=((ll)a+b)%mod; } template void sub(T& a,U b){ a=((ll)a-b%mod+mod)%mod; } template void mult(T& a,U b){ a=((ll)a*b)%mod; } ll modPow(ll a,ll p){ ll s=1; REP(i,30){ if((p>>i)&1) mult(s,a); mult(a,a); } return s; } ll modInv(ll a){ return modPow(a,mod-2); } string sq[61]; int len[61],wa[61],sk[61]; pi GanbaruZoi(int lv,int l,int r){ if(r<=l)return pi(0,1); if(l==0&&r==len[lv]) return pi(wa[lv],sk[lv]); int x=len[lv-1],y=x+sq[lv].size(); pi a(0,1),b(0,1); if(l