MOD = 10**9 + 7 def main(): import sys S = sys.stdin.readline().strip() n = len(S) if n == 0: print(0) return # Precompute base powers for rolling hash base = 911382487 mod = 10**18 + 3 prefix = [0] * (n + 1) pow_base = [1] * (n + 1) for i in range(n): prefix[i+1] = (prefix[i] * base + ord(S[i])) % mod pow_base[i+1] = (pow_base[i] * base) % mod # Compute hash for reverse string reversed_S = S[::-1] prefix_rev = [0] * (n + 1) for i in range(n): prefix_rev[i+1] = (prefix_rev[i] * base + ord(reversed_S[i])) % mod # Function to get hash of s[l..r] def get_hash(prefix, l, r): res = (prefix[r+1] - prefix[l] * pow_base[r - l + 1]) % mod return res dp = [[0] * n for _ in range(n)] # Precompute lengths in increasing order for length in range(1, n+1): for i in range(n - length + 1): j = i + length - 1 if i == j: dp[i][j] = 1 continue res = 1 # Case k=1, split into one part max_l = (length) // 2 for l in range(1, max_l + 1): # Check if left and right parts are equal left_i, left_j = i, i + l - 1 right_i, right_j = j - l + 1, j hash_left = get_hash(prefix, left_i, left_j) hash_right = get_hash(prefix, right_i, right_j) if hash_left == hash_right: next_i = i + l next_j = j - l if next_i <= next_j: res += dp[next_i][next_j] else: res += 1 # The middle part is empty, count as 1 way res %= MOD dp[i][j] = res % MOD print(dp[0][n-1] % MOD) if __name__ == "__main__": main()