Levko loves strings of length n, consisting of lowercase English letters, very much. He has one such string s. For each string t of length n, Levko defines its beauty relative to s as the number of pairs of indexes i, j (1 ≤ i ≤ j ≤ n), such that substring t[i..j] is lexicographically larger than substring s[i..j].

The boy wondered how many strings t are there, such that their beauty relative to s equals exactly k. Help him, find the remainder after division this number by 1000000007 (10⁹ + 7).

A substring s[i..j] of string s = s₁s₂... s_n is string s_is_{i  +  1}... s_j.

String x  =  x₁x₂... x_p is lexicographically larger than string y  =  y₁y₂... y_p, if there is such number r (r < p), that x₁  =  y₁,  x₂  =  y₂,  ... ,  x_r  =  y_r and x_{r  +  1} > y_{r  +  1}. The string characters are compared by their ASCII codes.