#pragma region template #include //#include // using cpp_int = boost::multiprecision::cpp_int; using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vld = vector; using vvld = vector; using vvvld = vector; using vs = vector; using pll = pair; using vp = vector; template using pqrev = priority_queue, greater>; #define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++) #define repb(i, n) for (ll i = (n)-1; i >= 0; i--) #define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++) #define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--) #define ALL(a) (a).begin(), (a).end() #define SZ(x) ((ll)(x).size()) #ifdef OJ_LOCAL #include "dump.hpp" #else #define dump(...) ((void)0) #endif constexpr ll INF = 1e+18; constexpr ld EPS = 1e-12L; constexpr ld PI = 3.14159265358979323846L; template constexpr T local([[maybe_unused]] const T &lcl, [[maybe_unused]] const T &oj) { #ifdef OJ_LOCAL return lcl; #else return oj; #endif } template constexpr bool chmax(S &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template constexpr bool chmin(S &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template T max(const vector &x) { return *max_element(ALL(x)); } template T min(const vector &x) { return *min_element(ALL(x)); } template pair argmax(const vector &x) { int idx = 0; T m = x[0]; repr(i, 1, SZ(x)) { if (chmax(m, x[i])) idx = i; } return {m, idx}; } template pair argmin(const vector &x) { int idx = 0; T m = x[0]; repr(i, 1, SZ(x)) { if (chmin(m, x[i])) idx = i; } return {m, idx}; } template T sum(const vector &x) { return accumulate(ALL(x), T(0)); } // last param -> T template vector makev(size_t a, T b) { return vector(a, b); } template auto makev(size_t sz, Args... args) { return vector(sz, makev(args...)); } template bool print_(const T &a) { cout << a; return true; } template bool print_(const vector &vec) { for (auto &a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } return false; } template bool print_(const vector> &vv) { for (auto &v : vv) { for (auto &a : v) { cout << a; if (&a != &v.back()) cout << " "; } if (&v != &vv.back()) cout << "\n"; } return false; } void print() { cout << "\n"; } template void print(Head &&head, Tail &&... tail) { bool f = print_(head); if (sizeof...(tail) != 0) cout << (f ? " " : "\n"); print(forward(tail)...); } #pragma endregion //* constexpr ll MOD = 1e9 + 7; /*/ constexpr ll MOD = 998244353; //*/ // ModInt // 参考:https://ei1333.github.io/luzhiled/snippets/math/mod-int.html // modはコンパイル時に決定 template struct ModInt { ll x; ModInt() : x(0) {} ModInt(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} constexpr ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } constexpr ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } constexpr ModInt &operator*=(const ModInt &p) { x = x * p.x % mod; return *this; } constexpr ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } constexpr ModInt operator-() { return ModInt(-x); } constexpr ModInt operator+() { return ModInt(x); } constexpr ModInt &operator++() { x++; if (x == mod) x = 0; return *this; } constexpr ModInt &operator--() { if (x == 0) x = mod; x--; return *this; } constexpr ModInt operator++(int) { ModInt result = *this; ++*this; return result; } constexpr ModInt operator--(int) { ModInt result = *this; --*this; return result; } friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) { return ModInt(lhs) += rhs; } friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) { return ModInt(lhs) -= rhs; } friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) { return ModInt(lhs) *= rhs; } friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) { return ModInt(lhs) /= rhs; } friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.x == rhs.x; } friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) { return lhs.x != rhs.x; } constexpr ModInt inverse() const { ll a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(ll n) { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { ll t; is >> t; a = ModInt(t); return (is); } }; using mint = ModInt; using vm = vector; using vvm = vector; constexpr int MAX_FAC = 2000010; mint fac[MAX_FAC], facinv[MAX_FAC]; void combInit() { fac[0] = mint(1); for (int i = 0; i < MAX_FAC - 1; i++) { fac[i + 1] = fac[i] * (i + 1); } facinv[MAX_FAC - 1] = fac[MAX_FAC - 1].inverse(); for (int i = MAX_FAC - 2; i >= 0; i--) { facinv[i] = facinv[i + 1] * (i + 1); } } mint comb(const ll a, const ll b) { assert(a < MAX_FAC); assert(b < MAX_FAC); if (a < 0 || b < 0 || b > a) { return mint(0); } mint ret(1); ret *= fac[a]; ret *= facinv[b]; ret *= facinv[a - b]; return ret; } mint multicomb(const ll a, const ll b) { return comb(a + b - 1, b); } #define PR(f) \ do { \ cout << ((f) ? "Yes" : "No") << "\n"; \ return; \ } while (0) // Disjoint Sparse Table // opは半群で結合律を満たす // 構築 O(N log N) クエリ O(1) template struct DisjointSparseTable { DisjointSparseTable() {} DisjointSparseTable(const vector &v) : n(v.size()) { log = 1; while ((1 << log) < n) log++; table.assign(log, v); for (int i = 1; i < log; i++) { int block_size = 1 << i; int en; bool rev = true; for (int st = 0; st < n; st += block_size) { en = min(st + block_size - 1, n - 1); if (rev) { for (int j = en - 1; j >= st; j--) { table[i][j] = op(table[i][j], table[i][j + 1]); } } else { for (int j = st + 1; j <= en; j++) { table[i][j] = op(table[i][j - 1], table[i][j]); } } rev = !rev; } } } // [l, r) 0 <= l < r <= n S fold(int l, int r) { assert(0 <= l && l < r && r <= n); r--; if (l == r) return table[0][l]; int i = 31 - __builtin_clz(l ^ r); return op(table[i][l], table[i][r]); } private: vector> table; int n, log; }; ll llmin(ll a, ll b) { return min(a, b); } ll llmax(ll a, ll b) { return max(a, b); } int intmin(int a, int b) { return min(a, b); } int intmax(int a, int b) { return max(a, b); } // ソート結果を配列のインデックスで得る // 配列自体はソートされない // {9, 5, 1, 3, 7} -> {2, 3, 1, 4, 0} template vector argSort(const vector &vec) { vector idx(vec.size()); iota(idx.begin(), idx.end(), 0); stable_sort(idx.begin(), idx.end(), [&](int l, int r) { return vec[l] < vec[r]; }); return idx; } namespace internal { vector sa_naive(const vector &s) { int n = int(s.size()); vector sa(n); iota(sa.begin(), sa.end(), 0); sort(sa.begin(), sa.end(), [&](int l, int r) { if (l == r) return false; while (l < n && r < n) { if (s[l] != s[r]) return s[l] < s[r]; l++; r++; } return l == n; }); return sa; } vector sa_doubling(const vector &s) { int n = int(s.size()); vector sa(n), rnk = s, tmp(n); iota(sa.begin(), sa.end(), 0); for (int k = 1; k < n; k *= 2) { auto cmp = [&](int x, int y) { if (rnk[x] != rnk[y]) return rnk[x] < rnk[y]; int rx = x + k < n ? rnk[x + k] : -1; int ry = y + k < n ? rnk[y + k] : -1; return rx < ry; }; sort(sa.begin(), sa.end(), cmp); tmp[sa[0]] = 0; for (int i = 1; i < n; i++) { tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0); } swap(tmp, rnk); } return sa; } // SA-IS, linear-time suffix array construction // Reference: // G. Nong, S. Zhang, and W. H. Chan, // Two Efficient Algorithms for Linear Time Suffix Array Construction template vector sa_is(const vector &s, int upper) { int n = int(s.size()); if (n == 0) return {}; if (n == 1) return {0}; if (n == 2) { if (s[0] < s[1]) { return {0, 1}; } else { return {1, 0}; } } if (n < THRESHOLD_NAIVE) { return sa_naive(s); } if (n < THRESHOLD_DOUBLING) { return sa_doubling(s); } vector sa(n); vector ls(n); for (int i = n - 2; i >= 0; i--) { ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]); } vector sum_l(upper + 1), sum_s(upper + 1); for (int i = 0; i < n; i++) { if (!ls[i]) { sum_s[s[i]]++; } else { sum_l[s[i] + 1]++; } } for (int i = 0; i <= upper; i++) { sum_s[i] += sum_l[i]; if (i < upper) sum_l[i + 1] += sum_s[i]; } auto induce = [&](const vector &lms) { fill(sa.begin(), sa.end(), -1); vector buf(upper + 1); copy(sum_s.begin(), sum_s.end(), buf.begin()); for (auto d : lms) { if (d == n) continue; sa[buf[s[d]]++] = d; } copy(sum_l.begin(), sum_l.end(), buf.begin()); sa[buf[s[n - 1]]++] = n - 1; for (int i = 0; i < n; i++) { int v = sa[i]; if (v >= 1 && !ls[v - 1]) { sa[buf[s[v - 1]]++] = v - 1; } } copy(sum_l.begin(), sum_l.end(), buf.begin()); for (int i = n - 1; i >= 0; i--) { int v = sa[i]; if (v >= 1 && ls[v - 1]) { sa[--buf[s[v - 1] + 1]] = v - 1; } } }; vector lms_map(n + 1, -1); int m = 0; for (int i = 1; i < n; i++) { if (!ls[i - 1] && ls[i]) { lms_map[i] = m++; } } vector lms; lms.reserve(m); for (int i = 1; i < n; i++) { if (!ls[i - 1] && ls[i]) { lms.push_back(i); } } induce(lms); if (m) { vector sorted_lms; sorted_lms.reserve(m); for (int v : sa) { if (lms_map[v] != -1) sorted_lms.push_back(v); } vector rec_s(m); int rec_upper = 0; rec_s[lms_map[sorted_lms[0]]] = 0; for (int i = 1; i < m; i++) { int l = sorted_lms[i - 1], r = sorted_lms[i]; int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n; int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n; bool same = true; if (end_l - l != end_r - r) { same = false; } else { while (l < end_l) { if (s[l] != s[r]) { break; } l++; r++; } if (l == n || s[l] != s[r]) same = false; } if (!same) rec_upper++; rec_s[lms_map[sorted_lms[i]]] = rec_upper; } auto rec_sa = sa_is(rec_s, rec_upper); for (int i = 0; i < m; i++) { sorted_lms[i] = lms[rec_sa[i]]; } induce(sorted_lms); } return sa; } } // namespace internal vector suffix_array(const vector &s, int upper) { assert(0 <= upper); for (int d : s) { assert(0 <= d && d <= upper); } auto sa = internal::sa_is(s, upper); return sa; } template vector suffix_array(const vector &s) { int n = int(s.size()); vector idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; }); vector s2(n); int now = 0; for (int i = 0; i < n; i++) { if (i && s[idx[i - 1]] != s[idx[i]]) now++; s2[idx[i]] = now; } return internal::sa_is(s2, now); } vector suffix_array(const string &s) { int n = int(s.size()); vector s2(n); for (int i = 0; i < n; i++) { s2[i] = s[i]; } return internal::sa_is(s2, 255); } // Reference: // T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park, // Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its // Applications template vector lcp_array(const vector &s, const vector &sa) { int n = int(s.size()); assert(n >= 1); vector rnk(n); for (int i = 0; i < n; i++) { rnk[sa[i]] = i; } vector lcp(n - 1); int h = 0; for (int i = 0; i < n; i++) { if (h > 0) h--; if (rnk[i] == 0) continue; int j = sa[rnk[i] - 1]; for (; j + h < n && i + h < n; h++) { if (s[j + h] != s[i + h]) break; } lcp[rnk[i] - 1] = h; } return lcp; } vector lcp_array(const string &s, const vector &sa) { int n = int(s.size()); vector s2(n); for (int i = 0; i < n; i++) { s2[i] = s[i]; } return lcp_array(s2, sa); } struct LCP { LCP(const string &s) : n(s.size()), sa(suffix_array(s)), lcpa(lcp_array(s, sa)) { init(); } template LCP(const vector &s) : n(s.size()), sa(suffix_array(s)), lcpa(lcp_array(s, sa)) { init(); } LCP(const vector &s, int upper) : n(s.size()), sa(suffix_array(s, upper)), lcpa(lcp_array(s, sa)) { init(); } // lcp(i, j): longest common prefix of S[i:], S[j:] int lcp(int i, int j) { if (i == j) return n - i; int x = argsa[i]; int y = argsa[j]; return dsp.fold(min(x, y), max(x, y)); } // eq(i, j, c): S.sub(i, c) == S.sub(j, c) bool eq(int i, int j, int c) { assert(i + c <= n); assert(j + c <= n); return lcp(i, j) >= c; } private: int n; vector sa, lcpa, argsa; DisjointSparseTable dsp; void init() { argsa = argSort(sa); dsp = DisjointSparseTable(lcpa); } }; void solve() { string s; cin >> s; ll n = SZ(s); vm dp(n/2+1, 0); dp[0] = 1; LCP l(s); rep(i, n/2){ repr(j, 1, n/2-i+1){ if(i!=n-i-j && l.eq(i, n-i-j, j)){ dp[i+j] += dp[i]; } } } print(sum(dp)); dump(dp); } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); //* solve(); /*/ ll _cases; cin >> _cases; while (_cases--) solve(); //*/ }