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.