Non-Overlapping Border Product

Given a string S of length L, a border of a string is defined as a non‐empty substring that is both a prefix and a suffix (but not equal to the entire string itself). In this problem, a border is considered valid only if the prefix and suffix do not overlap. Formally, for a prefix S[1 \ldots i] (with length i), a border of length k is valid if it satisfies

\(2\times k \le i\)

Let \(\mathrm{num}[i]\) denote the number of valid borders for the prefix S[1 \ldots i]. Your task is to compute the product:

\(\prod_{i=1}^{L} (\mathrm{num}[i] + 1) \mod (10^9+7)\)

Note: The condition \(2\times k \le i\) ensures that the prefix and the corresponding suffix do not overlap.

Example:

• For \(S = \verb!aaaaa!\):
  • For i = 4 (prefix \(\verb!aaaa!\)), the valid borders are a (length 1) and aa (length 2), so \(\mathrm{num}[4] = 2\).
  • For i = 5 (prefix \(\verb!aaaaa!\)), the valid borders are a and aa, so \(\mathrm{num}[5] = 2\).
• The final answer is the product \((num[1]+1)\times (num[2]+1)\times \cdots \times (num[L]+1)\) modulo \(10^9+7\).

inputFormat

The input consists of a single line containing the string S.

outputFormat

Output a single integer — the product \(\prod_{i=1}^{L} (\mathrm{num}[i] + 1)\) modulo \(10^9+7\).

sample

aaaaa

36