#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/599"

#include <iostream>
#include <vector>

#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/types.hpp"

#include <cstddef>
#include <cstdint>

namespace gwen {

/** @name 符号あり整数型 */
///@{
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
///@}

/** @name 符号なし整数型 */
///@{
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
///@}

/** @name ポインタサイズ・コンテナサイズ型 */
///@{
using usize = std::size_t;
using isize = std::ptrdiff_t;
///@}

/** @name 浮動小数点型 */
///@{
using f32 = float;
using f64 = double;
using f80 = long double;
///@}

/**
 * @brief 数値リテラル用のユーザー定義リテラル
 */
namespace literals {

/** @brief i64 型のリテラル */
constexpr i64 operator""_i64(unsigned long long n) { return static_cast<i64>(n); }
/** @brief u64 型のリテラル */
constexpr u64 operator""_u64(unsigned long long n) { return static_cast<u64>(n); }
/** @brief usize 型のリテラル */
constexpr usize operator""_zu(unsigned long long n) { return static_cast<usize>(n); }

}  // namespace literals

}  // namespace gwen
#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/hash/rolling_hash.hpp"

// std
#include <algorithm>
#include <cassert>
#line 7 "/home/chabudaisanta/lib/gwen/include/gwen/hash/rolling_hash.hpp"

#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/mod/mod61.hpp"

#line 4 "/home/chabudaisanta/lib/gwen/include/gwen/mod/mod61.hpp"
#include <concepts>
#include <type_traits>

#line 8 "/home/chabudaisanta/lib/gwen/include/gwen/mod/mod61.hpp"

namespace gwen {

/**
 * @brief 2^61 - 1 を法とするモジュラ演算クラス
 * @details 主にローリングハッシュなどで利用される、高速なモジュラ演算を提供するクラスです。
 */
struct ModInt61 {
private:
    using m61 = ModInt61;
    static constexpr u64 mod61 = (1ull << 61) - 1;
    static constexpr u64 msk61 = (1ull << 61) - 1;

    u64 tr;

    static constexpr u64 calc_mod(u64 x) {
        u64 res = (x >> 61) + (x & msk61);
        if (res >= mod61) res -= mod61;
        return res;
    }

    static constexpr u64 mul_mod(u64 a, u64 b) {
        u128 t = static_cast<u128>(a) * b;
        u64 res = static_cast<u64>(t >> 61) + static_cast<u64>(t & msk61);
        if (res >= mod61) res -= mod61;
        return res;
    }

public:
    /**
     * @brief 法を取得する
     * @return 法 (2^61 - 1)
     */
    static constexpr u64 mod() { return mod61; }

    /**
     * @brief デフォルトコンストラクタ (0で初期化)
     */
    constexpr ModInt61() : tr(0) {}

    /**
     * @brief 符号なし整数からのコンストラクタ
     */
    template <std::unsigned_integral T> constexpr ModInt61(T x) {
        static_assert(sizeof(T) <= sizeof(u64), "T must be 64-bit or smaller");
        tr = calc_mod(static_cast<u64>(x));
    }

    /**
     * @brief 符号付き整数からのコンストラクタ
     */
    template <std::signed_integral T> constexpr ModInt61(T x) {
        static_assert(sizeof(T) <= sizeof(u64), "T must be 64-bit or smaller");
        if (x < 0) {
            i64 v = x % static_cast<i64>(mod61);
            if (v < 0) v += mod61;
            tr = v;
        }
        else {
            tr = calc_mod(static_cast<u64>(x));
        }
    }

    /**
     * @brief 現在の値を返す
     * @return 0以上 2^61-2 以下の整数
     */
    constexpr u64 val() const { return tr; }

    constexpr m61& operator+=(const m61& x) {
        tr += x.tr;
        if (tr >= mod61) tr -= mod61;
        return *this;
    }
    constexpr m61& operator-=(const m61& x) {
        if (tr < x.tr) tr += mod61;
        tr -= x.tr;
        return *this;
    }
    constexpr m61& operator*=(const m61& x) {
        tr = mul_mod(tr, x.tr);
        return *this;
    }
    constexpr m61& operator/=(const m61& x) { return *this *= x.inv(); }

    /**
     * @brief 単項マイナス演算子
     */
    constexpr m61 operator-() const { return tr == 0 ? m61() : m61(mod61 - tr); }

    friend constexpr m61 operator+(const m61& lhs, const m61& rhs) { return m61(lhs) += rhs; }
    friend constexpr m61 operator-(const m61& lhs, const m61& rhs) { return m61(lhs) -= rhs; }
    friend constexpr m61 operator*(const m61& lhs, const m61& rhs) { return m61(lhs) *= rhs; }
    friend constexpr m61 operator/(const m61& lhs, const m61& rhs) { return m61(lhs) /= rhs; }

    friend constexpr bool operator==(const m61& lhs, const m61& rhs) { return lhs.tr == rhs.tr; }
    friend constexpr bool operator!=(const m61& lhs, const m61& rhs) { return lhs.tr != rhs.tr; }

    /**
     * @brief 累乗を計算する
     * @param x 指数
     * @return this^x
     */
    template <std::integral T> constexpr m61 pow(T x) const {
        if constexpr (std::is_signed_v<T>) {
            assert(x >= 0);
        }
        m61 res(1);
        m61 tmp(*this);
        while (x) {
            if (x & 1) res *= tmp;
            tmp *= tmp;
            x >>= 1;
        }
        return res;
    }

    /**
     * @brief 逆元を計算する
     * @return this^(-1)
     */
    constexpr m61 inv() const {
        assert(tr != 0 && "ModInt61::inv(): division by zero");
        return pow(mod61 - 2);
    }
};

}  // namespace gwen
#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/utils/xorshift.hpp"

// std
#include <chrono>
#include <random>

#line 8 "/home/chabudaisanta/lib/gwen/include/gwen/utils/xorshift.hpp"

namespace gwen {

namespace internal {
struct XorShift {
    u64 x = []() {
        u64 seed = static_cast<u64>(std::random_device{}()) ^
                   static_cast<u64>(std::chrono::steady_clock::now().time_since_epoch().count());
        return seed == 0 ? 1 : seed;
    }();

    u64 get() {
        x ^= x >> 4;
        x ^= x << 37;
        x ^= x >> 11;
        return x;
    }
};
}  // namespace internal

/**
 * @brief 64ビットの乱数を生成します。
 * @details 内部で static な xorshift 乱数生成器を使用しているため、**スレッドセーフではありません**。
 * 計算量: \f$O(1)\f$
 * @return 64ビットの乱数値
 */
inline u64 rand64() {
    static internal::XorShift rng;
    return rng.get();
}

/**
 * @brief 32ビットの乱数を生成します。
 * @details 内部で `rand64()` を呼び出しているため、**スレッドセーフではありません**。
 * 計算量: \f$O(1)\f$
 * @return 32ビットの乱数値
 */
inline u32 rand32() { return rand64() >> 32; }

/**
 * @brief `0` 以上 `r - 1` 以下の32ビット乱数を生成します。
 * @details 内部で `rand64()` を呼び出しているため、**スレッドセーフではありません**。
 * 計算量: \f$O(1)\f$
 * @param r 生成する乱数の上限 (排他)
 * @return `[0, r)` の乱数値
 */
inline u32 rand32(u32 r) { return ((rand64() >> 32) * r) >> 32; }

/**
 * @brief `l` 以上 `r - 1` 以下の32ビット乱数を生成します。
 * @details 内部で `rand64()` を呼び出しているため、**スレッドセーフではありません**。
 * 計算量: \f$O(1)\f$
 * @param l 生成する乱数の下限 (包含)
 * @param r 生成する乱数の上限 (排他)
 * @pre `l <= r`
 * @return `[l, r)` の乱数値
 */
inline u32 rand32(u32 l, u32 r) { return rand32(r - l) + l; }

}  // namespace gwen
#line 11 "/home/chabudaisanta/lib/gwen/include/gwen/hash/rolling_hash.hpp"

namespace gwen {
namespace rhash {

/**
 * @brief セグメント木等に乗せるためのローリングハッシュ用モノイド
 * @details `ID` ごとに独立した基数 `r` を静的に生成して持ちます。
 *
 * @tparam ID 異なる基数を持たせるための識別子（デフォルトは0）
 */
template <i32 ID = 0> struct rolling_hash_monoid {
    /// @brief 基数 (法 $2^{61}-1$ 上での乱数)
    static inline const ModInt61 r = ModInt61(rand64() % (ModInt61::mod() - 2) + 2);

    /**
     * @brief ハッシュ値とその長さ（基数のべき乗）の組を表す構造体
     */
    struct S {
        ModInt61 v, p;
        friend bool operator==(const S& a, const S& b) = default;
        friend bool operator!=(const S& a, const S& b) = default;
    };

    /**
     * @brief 2つのハッシュ値を結合します。
     * @details 左側のハッシュ値 `a` に、右側のハッシュ値 `b` を連結します。
     * 計算量: \f$O(1)\f$
     * @param a 左側のハッシュ
     * @param b 右側のハッシュ
     * @return 結合されたハッシュ
     */
    static S op(S a, S b) {
        ModInt61 v = b.v * a.p + a.v;
        ModInt61 p = a.p * b.p;
        return {v, p};
    }

    /**
     * @brief 単位元（空文字列のハッシュ）を返します。
     * @details 計算量: \f$O(1)\f$
     * @return 単位元
     */
    static S e() { return {ModInt61(0), ModInt61(1)}; }

    /**
     * @brief 1文字からハッシュ（長さ1の要素）を生成します。
     * @details 計算量: \f$O(1)\f$
     * @tparam T 文字や整数の型
     * @param x 要素
     * @return 生成されたハッシュ要素
     */
    template <typename T> static S unit(T x) { return {ModInt61(x), r}; }

    /**
     * @brief イテレータ範囲からハッシュ値を計算します。
     * @details 計算量: \f$O(N)\f$ (範囲の長さに比例)
     * @tparam Iterator イテレータの型
     * @param begin 範囲の開始
     * @param end 範囲の終端
     * @return 範囲全体のハッシュ
     */
    template <typename Iterator> static S range(Iterator begin, Iterator end) {
        ModInt61 v = 0, p = 1;
        for (auto it = begin; it != end; ++it) {
            v += p * ModInt61(*it);
            p *= r;
        }
        return {v, p};
    }

    /**
     * @brief イテレータ範囲をセグメント木用の要素配列（`std::vector<S>`）に変換します。
     * @details 計算量: \f$O(N)\f$
     * @tparam Iterator イテレータの型
     * @param begin 範囲の開始
     * @param end 範囲の終端
     * @return セグメント木構築用の配列
     */
    template <typename Iterator> static std::vector<S> build(Iterator begin, Iterator end) {
        std::vector<S> res;
        for (auto it = begin; it != end; ++it) {
            res.push_back(unit(*it));
        }
        return res;
    }

    /**
     * @brief シーケンスをセグメント木用の要素配列（`std::vector<S>`）に変換します。
     * @details 計算量: \f$O(N)\f$
     * @tparam Container シーケンスの型
     * @param seq 変換する対象のシーケンス
     * @return セグメント木構築用の配列
     */
    template <typename Container> static std::vector<S> build(const Container& seq) {
        std::vector<S> res;
        if constexpr (requires { std::size(seq); }) {
            res.reserve(std::size(seq));
        }
        for (const auto& x : seq) {
            res.push_back(unit(x));
        }
        return res;
    }
};

/**
 * @brief 基数のべき乗をメモ化する内部クラス
 * @tparam ID モノイドと共通の識別子
 */
template <i32 ID> struct PowerTable {
    static std::vector<ModInt61>& data() {
        static std::vector<ModInt61> table{ModInt61(1)};
        return table;
    }

    static void ensure(i32 n) {
        auto& t = data();
        const ModInt61 base = rolling_hash_monoid<ID>::r;
        while (static_cast<i32>(t.size()) <= n) {
            t.push_back(t.back() * base);
        }
    }

    static ModInt61 pow(i32 len) {
        assert(0 <= len && len < static_cast<i32>(data().size()));
        return data()[static_cast<usize>(len)];
    }
};

}  // namespace rhash

/**
 * @brief 静的文字列用のローリングハッシュクラス
 * @details 構築に \f$O(N)\f$ かかりますが、以降は任意の部分文字列のハッシュを \f$O(1)\f$ で取得できます。
 *
 * @tparam ID 異なる基数を持たせるための識別子（デフォルトは0）
 */
template <i32 ID = 0> class RollingHash {
public:
    using Monoid = rhash::rolling_hash_monoid<ID>;
    using S = typename Monoid::S;

private:
    i32 n;
    std::vector<ModInt61> suf;

public:
    /**
     * @brief シーケンスからローリングハッシュを構築します。
     * @details 計算量: \f$O(N)\f$
     * @tparam Container シーケンスの型 (std::string や std::vector など)
     * @param seq ハッシュ化する対象のシーケンス
     */
    template <typename Container>
    explicit RollingHash(const Container& seq) : n(static_cast<i32>(std::size(seq))), suf(n + 1, ModInt61(0)) {
        rhash::PowerTable<ID>::ensure(n);
        for (i32 i = n - 1; i >= 0; --i) {
            suf[i] = ModInt61(seq[i]) + Monoid::r * suf[i + 1];
        }
    }

    /**
     * @brief 文字列の長さを返します。
     * @details 計算量: \f$O(1)\f$
     * @return 文字列の長さ
     */
    i32 size() const { return n; }

    /**
     * @brief 部分区間 `[l, r)` のハッシュ値を取得します。
     * @details 先頭の要素が基数の $0$
     * 乗に対応するように正規化されたハッシュと、その長さ（基数のべき乗）の組を返します。 計算量: \f$O(1)\f$
     * @param l 区間の開始インデックス (包含)
     * @param r 区間の終了インデックス (排他)
     * @pre `0 <= l <= r <= n`
     * @return 部分区間のハッシュ値
     */
    S get(i32 l, i32 r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return Monoid::e();
        const i32 len = r - l;
        const ModInt61 rp = rhash::PowerTable<ID>::pow(len);
        ModInt61 v = suf[l] - suf[r] * rp;
        return {v, rp};
    }

    /**
     * @brief 区間 `[l, r)` を左に `k` 文字巡回シフトしたハッシュを取得します。
     * @details 計算量: \f$O(1)\f$
     * @param l 区間の開始インデックス
     * @param r 区間の終了インデックス
     * @param k シフトする文字数 (負の場合は右シフト)
     * @pre `0 <= l <= r <= n`
     * @return 巡回シフト後のハッシュ値
     */
    S rotl(i32 l, i32 r, i32 k) const {
        assert(0 <= l && l <= r && r <= n);
        const i32 len = r - l;
        if (len == 0) return Monoid::e();
        k %= len;
        if (k < 0) k += len;
        if (k == 0) return get(l, r);
        return Monoid::op(get(l + k, r), get(l, l + k));
    }

    /**
     * @brief 区間 `[l, r)` を右に `k` 文字巡回シフトしたハッシュを取得します。
     * @details 計算量: \f$O(1)\f$
     * @param l 区間の開始インデックス
     * @param r 区間の終了インデックス
     * @param k シフトする文字数 (負の場合は左シフト)
     * @pre `0 <= l <= r <= n`
     * @return 巡回シフト後のハッシュ値
     */
    S rotr(i32 l, i32 r, i32 k) const {
        assert(0 <= l && l <= r && r <= n);
        const i32 len = r - l;
        if (len == 0) return Monoid::e();
        k %= len;
        if (k < 0) k += len;
        if (k == 0) return get(l, r);
        return Monoid::op(get(r - k, r), get(l, r - k));
    }

    /**
     * @brief 2つの部分文字列が一致するか判定します。
     * @details 計算量: \f$O(1)\f$
     * @param l1 1つ目の部分文字列の開始
     * @param r1 1つ目の部分文字列の終了
     * @param l2 2つ目の部分文字列の開始
     * @param r2 2つ目の部分文字列の終了
     * @return 一致すれば `true`
     */
    bool equal(i32 l1, i32 r1, i32 l2, i32 r2) const {
        assert(0 <= l1 && l1 <= r1 && r1 <= n);
        assert(0 <= l2 && l2 <= r2 && r2 <= n);
        if (r1 - l1 != r2 - l2) return false;
        if (l1 == r1) return true;
        return get(l1, r1) == get(l2, r2);
    }

    /**
     * @brief 接尾辞 `[l1, n)` と `[l2, n)` の最長共通接頭辞 (LCP) の長さを求めます。
     * @details 二分探索を用いて計算します。
     * 計算量: \f$O(\log N)\f$
     * @param l1 1つ目の開始インデックス
     * @param l2 2つ目の開始インデックス
     * @return LCP の長さ
     */
    i32 lcp(i32 l1, i32 l2) const {
        assert(0 <= l1 && l1 <= n);
        assert(0 <= l2 && l2 <= n);
        i32 lo = 0, hi = std::min(n - l1, n - l2) + 1;
        while (hi - lo > 1) {
            i32 mid = (lo + hi) / 2;
            if (equal(l1, l1 + mid, l2, l2 + mid))
                lo = mid;
            else
                hi = mid;
        }
        return lo;
    }
};

}  // namespace gwen
#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/mod/modint.hpp"
// https://rsk0315.hatenablog.com/entry/2022/11/27/060616
#line 6 "/home/chabudaisanta/lib/gwen/include/gwen/mod/modint.hpp"

#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/alge/ring.hpp"

#line 4 "/home/chabudaisanta/lib/gwen/include/gwen/alge/ring.hpp"

namespace gwen {

/**
 * @brief 環(Ring)の要件を定義するコンセプト
 */
template <typename T>
concept ring = requires(T a, T b) {
    { a + b } -> std::same_as<T>;
    { a - b } -> std::same_as<T>;
    { a * b } -> std::same_as<T>;
    { a += b } -> std::same_as<T&>;
    { a -= b } -> std::same_as<T&>;
    { a *= b } -> std::same_as<T&>;
};

}  // namespace gwen
#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/mod/mod.hpp"

#line 4 "/home/chabudaisanta/lib/gwen/include/gwen/mod/mod.hpp"
#include <utility>

#line 7 "/home/chabudaisanta/lib/gwen/include/gwen/mod/mod.hpp"

namespace gwen {

/**
 * @brief べき乗余 $x^n \pmod{m}$ を返す
 * @details 計算量: $O(\log n)$
 * @param x 底
 * @param n 指数
 * @param m 法（デフォルト: 998244353）
 * @return $x^n \bmod m$
 */
i64 pow_mod(i64 x, i64 n, i64 m = 998244353) {
    if (x == 0) return (n ? 0 : 1);
    x %= m;
    i64 res = 1;
    while (n) {
        if (n & 1) res = (res * x) % m;
        x = (x * x) % m;
        n >>= 1;
    }
    return res;
}

/**
 * @brief 逆元 $a^{-1} \pmod{m}$ を返す
 * @details 拡張ユークリッド互除法を用いる。計算量: $O(\log m)$
 * @param a 逆元を求める値（$a \ne 0$）
 * @param m 法（デフォルト: 998244353）
 * @pre $a \ne 0$
 * @return $a^{-1} \bmod m$
 */
i64 inv_mod(i64 a, i64 m = 998244353) {
    assert(a != 0 && "inv_mod(0, m): inverse does not exist");
    i64 b = m, u = 1, v = 0;
    while (b) {
        i64 t = a / b;
        a -= t * b;
        std::swap(a, b);
        u -= t * v;
        std::swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

/**
 * @brief 64ビット値の逆元 $a^{-1} \pmod{m}$ を返す
 * @details 内部で `i128` を利用する拡張ユークリッド互除法を用いる。計算量: $O(\log m)$
 * @param a 逆元を求める値
 * @param m 法
 * @pre $\gcd(a, m) = 1$
 * @return $a^{-1} \bmod m$
 */
u64 inv_mod_64(u64 a, u64 m) {
    i128 s = m, t = a;
    i128 x = 0, y = 1;

    while (t) {
        i128 u = s / t;
        s -= t * u;
        x -= y * u;
        std::swap(s, t);
        std::swap(x, y);
    }
    // assert(s == 1); // gcd(a,m)が1でなければ逆元は存在しない
    return (x % m + m) % m;
}

}  // namespace gwen
#line 10 "/home/chabudaisanta/lib/gwen/include/gwen/mod/modint.hpp"

namespace gwen {

/**
 * @brief modint型としての要件を定義するコンセプト
 * ACLのmodintと互換性のあるインターフェースを持つことを要求する。
 */
template <typename T>
concept modint = ring<T> && requires(T a, T b, u64 n) {
    { a / b } -> std::same_as<T>;
    { a /= b } -> std::same_as<T&>;
    { a.val() } -> std::integral;
    { T::mod() } -> std::integral;
    { a.inv() } -> std::same_as<T>;
    { a.pow(n) } -> std::same_as<T>;
};

/**
 * @brief 実行時に法を設定可能なモジュラ演算クラス (64bit)
 * @details 内部で Montgomery 乗算を用いることで高速化されている。
 */
struct DynamicModInt64 {
private:
    using m64 = DynamicModInt64;
    static inline u64 n = 1;
    static inline u64 ns = 0;
    static inline u64 r2 = 0;
    static inline constexpr u64 msk = -1;

    u64 reduce_mul(u64 a, u64 b) const {
        u128 t = static_cast<u128>(a) * b;
        u128 m = (t * ns) & msk;
        a = (m * n + t) >> 64;
        return a < n ? a : a - n;
    }

    u64 tr;

public:
    /**
     * @brief クラス全体の法を設定する
     * @param n_ 設定する法 (奇数かつ 1 <= n_ < 2^62)
     */
    static void set_mod(u64 n_) {
        assert(n_ < (1ull << 62));
        assert(n_ & 1);
        n = n_;
        ns = n;
        for (i32 i = 0; i < 5; ++i) ns *= 2 - ns * n;
        assert(ns * n == 1);
        ns = -ns;
        r2 = -static_cast<u128>(n) % n;
    }

    /**
     * @brief 現在設定されている法を取得する
     * @return 法
     */
    static u64 mod() { return n; }

    /**
     * @brief デフォルトコンストラクタ (0で初期化)
     */
    DynamicModInt64() : tr(0) {}

    /**
     * @brief 符号なし整数からのコンストラクタ
     */
    template <std::unsigned_integral T> DynamicModInt64(T x) {
        static_assert(sizeof(T) <= sizeof(u64), "T must be 64-bit or smaller");
        tr = reduce_mul(static_cast<u64>(x), r2);
    }

    /**
     * @brief 符号付き整数からのコンストラクタ
     */
    template <std::signed_integral T> DynamicModInt64(T x) : tr(0) {
        static_assert(sizeof(T) <= sizeof(u64), "T must be 64-bit or smaller");
        if (x < 0) {
            sub(m64{static_cast<u64>(-static_cast<i64>(x))});
        }
        else {
            tr = reduce_mul(static_cast<u64>(x), r2);
        }
    }

    /**
     * @brief 現在の値を返す
     */
    u64 val() const { return reduce_mul(tr, 1); }

    // basic operation
    m64& sub(const m64& x) {
        if (tr < x.tr) tr += n;
        tr -= x.tr;
        return *this;
    }
    m64& add(const m64& x) {
        tr += x.tr;
        if (tr >= n) tr -= n;
        return *this;
    }
    m64& mul(const m64& x) {
        tr = reduce_mul(tr, x.tr);
        return *this;
    }

    m64& operator+=(const m64& x) { return add(x); }
    m64& operator-=(const m64& x) { return sub(x); }
    m64& operator*=(const m64& x) { return mul(x); }
    m64& operator/=(const m64& x) { return mul(x.inv()); }

    /**
     * @brief 単項マイナス演算子
     */
    m64 operator-() const { return tr == 0 ? m64() : m64(n - val()); }

    friend m64 operator+(const m64& lhs, const m64& rhs) { return m64(lhs) += rhs; }
    friend m64 operator-(const m64& lhs, const m64& rhs) { return m64(lhs) -= rhs; }
    friend m64 operator*(const m64& lhs, const m64& rhs) { return m64(lhs) *= rhs; }
    friend m64 operator/(const m64& lhs, const m64& rhs) { return m64(lhs) /= rhs; }

    friend bool operator==(const m64& lhs, const m64& rhs) { return lhs.tr == rhs.tr; }
    friend bool operator!=(const m64& lhs, const m64& rhs) { return lhs.tr != rhs.tr; }

    /**
     * @brief 逆元を計算する
     */
    m64 inv() const {
        u64 v = val();
        assert(v != 0 && "DynamicModInt64::inv(): division by zero");
        return m64(inv_mod_64(v, n));
    }

    /**
     * @brief 累乗を計算する
     */
    template <std::integral T> m64 pow(T x) const {
        if constexpr (std::is_signed_v<T>) {
            assert(x >= 0);
        }
        m64 res(1);
        m64 tmp(*this);
        while (x) {
            if (x & 1) res.mul(tmp);
            tmp.tr = reduce_mul(tmp.tr, tmp.tr);
            x >>= 1;
        }
        return res;
    }
};

}  // namespace gwen
#line 3 "/home/chabudaisanta/lib/gwen/include/gwen/core/constants.hpp"

namespace gwen {

/** @brief 頻出の素数モジュロ (998244353) */
constexpr i32 mod998 = 998244353;
/** @brief 頻出の素数モジュロ (1000000007) */
constexpr i32 mod107 = 1000000007;
/** @brief 頻出の素数モジュロ (1000000009) */
constexpr i32 mod109 = 1000000009;
/** @brief 頻出の素数モジュロ (2147483647) */
constexpr i32 mod31 = 2147483647;
/** @brief ローリングハッシュ等で使われる素数モジュロ ((1<<61)-1) */
constexpr i64 mod61 = (1LL << 61) - 1;

/** @brief int型の十分大きな値 (1001001001) */
constexpr i32 iINF = 1001001001;
/** @brief i64型の十分大きな値 ((1LL<<60)+1) */
constexpr i64 liINF = (1LL << 60) + 1;

/** @brief 改行文字 */
constexpr char EL = '\n';
/** @brief 空白文字 */
constexpr char SPA = ' ';

}  // namespace gwen
#line 2 "/home/chabudaisanta/lib/gwen/include/gwen/dump.hpp"

#line 4 "/home/chabudaisanta/lib/gwen/include/gwen/dump.hpp"
#include <format>
#line 6 "/home/chabudaisanta/lib/gwen/include/gwen/dump.hpp"
#include <source_location>
#include <string>
#include <string_view>
#if __has_include(<unistd.h>)
#include <unistd.h>
#endif

#line 14 "/home/chabudaisanta/lib/gwen/include/gwen/dump.hpp"

namespace gwen {

namespace internal {

constexpr std::string_view basename(std::string_view path) {
    auto pos = path.find_last_of("/\\");
    return pos == std::string_view::npos ? path : path.substr(pos + 1);
}

template <typename... Args> constexpr bool is_empty_args(Args&&... args) { return sizeof...(args) == 0; }

template <typename T>
concept dumpable = requires(const T& t) {
    { t.dump() } -> std::convertible_to<std::string>;
};

template <typename T>
concept value_formattable = requires(const T& t) {
    { t.val() } -> std::formattable<char>;
};

struct Color {
    const char* code;
    friend std::ostream& operator<<(std::ostream& os, const Color& c) {
#if __has_include(<unistd.h>)
        static const bool tty = ::isatty(2);
        if (tty) os << c.code;
#else
        os << c.code;
#endif
        return os;
    }
};

constexpr Color RED{"\033[1;31m"};
constexpr Color GREEN{"\033[1;32m"};
constexpr Color YELLOW{"\033[1;33m"};
constexpr Color BLUE{"\033[1;34m"};
constexpr Color MAGENTA{"\033[1;35m"};
constexpr Color CYAN{"\033[1;36m"};
constexpr Color WHITE{"\033[1;37m"};
constexpr Color RESET{"\033[0m"};

}  // namespace internal

/**
 * @brief 変数の内容を標準エラー出力 (std::cerr) に出力するユーティリティ
 *
 * dumpable な型や value_formattable な型、および std::format で出力可能な型に対応しています。
 * 主にローカル環境でのデバッグ出力に利用されます。
 *
 * @tparam Args 出力する変数の型
 * @param args 出力する変数のリスト
 */
template <typename... Args> void dump(Args&&... args) {
    auto f = [](auto&& arg) {
        using T = std::remove_cvref_t<decltype(arg)>;
        if constexpr (internal::dumpable<T>) {
            return arg.dump();
        }
        else if constexpr (internal::value_formattable<T>) {
            return std::format("{}", arg.val());
        }
        else if constexpr (std::formattable<T, char>) {
            return std::format("{}", arg);
        }
        else {
            return "[unformattable token]";
        }
    };
    usize cnt = 0;
    auto sz = sizeof...(args);
    ((std::cerr << f(args) << (++cnt < sz ? ",\n" : "\n")), ...);
}

/**
 * @brief ローカル環境 (LOCAL マクロ定義時) でのみ動作するデバッグ出力マクロ
 *
 * 変数名と合わせて dump 関数を呼び出します。提出時は何も出力しません。
 *
 * @param ... 出力対象の変数（カンマ区切り）
 */
#ifdef LOCAL
#define DUMP(...)                                                                                                     \
    do {                                                                                                              \
        auto loc = std::source_location::current();                                                                   \
        std::cerr << ::gwen::internal::CYAN << "[gwen::DUMP @ " << ::gwen::internal::basename(loc.file_name()) << ':' \
                  << loc.line() << "]\n"                                                                              \
                  << ::gwen::internal::RESET;                                                                         \
        constexpr std::string_view __vars_sv = #__VA_ARGS__;                                                          \
        if constexpr (__vars_sv.empty() || __vars_sv.find_first_not_of(" \t\r\n") == std::string_view::npos) {        \
            std::cerr << ::gwen::internal::RED << "[empty]\n" << ::gwen::internal::RESET;                             \
        }                                                                                                             \
        else {                                                                                                        \
            std::cerr << ::gwen::internal::YELLOW << "[vars]\n"                                                       \
                      << ::gwen::internal::RESET << #__VA_ARGS__ << "\n"                                              \
                      << ::gwen::internal::GREEN << "[dump]\n"                                                        \
                      << ::gwen::internal::RESET;                                                                     \
            ::gwen::dump(__VA_ARGS__);                                                                                \
        }                                                                                                             \
    } while (0)
#else
#define DUMP(...) \
    do {          \
    } while (0)
#endif
}  // namespace gwen
#line 11 "test.cpp"

using namespace std;
using namespace gwen;

int main() {
    using mint = DynamicModInt64;
    mint::set_mod(mod107);
    string S; cin >> S;
    const i32 N = S.size();
    const i32 K = N / 2;

    auto rh = RollingHash(S);
    mint ans = 0;
    vector<mint> dp(K + 1);
    dp[0] = 1;
    for(i32 i = 0; i <= K; ++i) {
        ans += dp[i];
        for(i32 j = i + 1; j <= K; ++j) {
            bool ok = rh.equal(i, j, N-j, N-i);
            if(ok) dp[j] += dp[i];
        }
    }
    cout << ans.val() << EL;

    return 0;
}