#include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; template using vc = vector; template using vvc = vc>; using pi = pair; using pl = pair; using vi = vc; using vvi = vvc; using vl = vc; using vvl = vvc; #define rep(i,a,b) for (int i = (int)(a); i < (int)(b); i++) #define irep(i,a,b) for (int i = (int)(a); i > (int)(b); i--) #define all(a) a.begin(),a.end() #define print(n) cout << n << '\n' #define pritn(n) print(n) #define printv(n,a) {copy(all(n),ostream_iterator(cout," ")); cout<<"\n";} #define printvv(n,a) {for(auto itr:n) printv(itr,a);} #define rup(a,b) (a+b-1)/b #define input(A,N) rep(i,0,N) cin>>A[i] #define chmax(a,b) a = max(a,b) #define chmin(a,b) a = min(a,b) //const int mod = 998'244'353; //const ll mod = 1'000'000'009; //const ll mod = 67'280'421'310'721; template< ll mod > struct mint{ long long x; mint(long long x=0):x((x%mod+mod)%mod){} mint operator-() const{ return mint(-x); } mint& operator+=(const mint& a){ if((x+=a.x)>=mod)x-=mod; return *this; } mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod)x-=mod; return *this; } mint& operator*=(const mint& a){ (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const{ mint res(*this); return res+=a; } mint operator-(const mint& a) const{ mint res(*this); return res-=a; } mint operator*(const mint& a) const{ mint res(*this); return res*=a; } mint pow(long long n) const { assert(0 <= n); mint a = *this, r = 1; while (n) { if (n & 1) r *= a; a *= a; n >>= 1; } return r; } mint inv() const{ return pow(mod-2); } mint& operator/=(const mint& a){ return (*this)*=a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } bool operator==(const mint& a) const { return x == a.x; } bool operator<(const mint& a) const{ return x < a.x; } }; const ll B = 100; //const ll m2 = 67'280'421'310'721; //const ll m2 = 998244353; const ll m2 = (1LL<<61)-1LL; struct rhash{ string s; int n; vc> sum; vc> powb; rhash(string s):s(s){ n = s.size(); sum = vc>(n+1,0); powb = vc>(n+1,1); for(int i = 0;i(B); sum[i+1] += mint(s[i]); powb[i+1] = powb[i]*mint(B); } } mint get(int l,int r){ return sum[r]-sum[l]*powb[r-l]; } }; const ll m1 = 1'000'000'009; mint dfs(int l,int r,vi&vis,rhash&hash,vc>&dp){ if(vis[l])return dp[l]; if(r<=l) return 1; mint now(1); int L = l,R = r; while(L>s; int n = s.size(); rhash hash(s); vc> dp(n,0); vi vis(n,0); print(dfs(0,n-1,vis,hash,dp)); //system("pause"); return 0; }