String Transformation Count

Given a lowercase alphabet string \(s\), you are allowed to perform the following operation any number of times:

1. Choose an index \(p\) such that \(1 \le p < |s|\) and change \(s_p\) to the next letter (in lexicographical order) and \(s_{p+1}\) to the previous letter.
2. Alternatively, change \(s_p\) to the previous letter and \(s_{p+1}\) to the next letter.

In each operation, the string must remain a valid lowercase string, which means you cannot decrement the letter a (i.e. perform a -1 operation on a).

After applying an arbitrary number of operations, determine how many distinct strings can be obtained modulo \(10^9+7\).

Observation: Notice that each operation adds \(+1\) to one character and \(-1\) to its neighbor so that the overall sum of the positions (when interpreting letters as \(0\) for \(a\), \(1\) for \(b\), ..., \(25\) for \(z\)) remains invariant. Therefore, the reachable strings are exactly those strings \(t\) of the same length with entries in \([0,25]\) and with total sum equal to \(S = \sum_{i=1}^{|s|}(s_i - a)\). The problem reduces to counting the number of solutions \(x_1 + x_2 + \cdots + x_n = S\) where \(0 \le x_i \le 25\) for \(1 \le i \le n\).

This can be solved using the inclusion–exclusion principle. More precisely, the number of solutions is given by:

[ \text{ans} = \sum_{i=0}^{\lfloor S/26 \rfloor} (-1)^i \binom{n}{i} \binom{S - 26 \cdot i + n - 1}{n - 1} \pmod{10^9+7}, ]

where \(n = |s|\) and all binomial coefficients are computed modulo \(10^9+7\). Use efficient precomputation of factorials and modular inverses to compute these terms.

inputFormat

The input consists of a single line containing the string \(s\) (only lowercase letters).

outputFormat

Output a single integer — the number of distinct strings that can be obtained, modulo \(10^9+7\).

sample

ab

2