結果
| 問題 | No.599 回文かい |
| コンテスト | |
| ユーザー |
 chabudaisanta
|
| 提出日時 | 2026-07-18 02:44:57 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 75 ms / 4,000 ms |
| + 586µs | |
| コード長 | 30,202 bytes |
| 記録 | |
| コンパイル時間 | 4,094 ms |
| コンパイル使用メモリ | 227,588 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-18 02:45:05 |
| 合計ジャッジ時間 | 5,859 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
#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;
}