Левко очень любит строки длины n, состоящие из строчных латинских букв. У него есть одна такая строка s. Для каждой строки t длины n Левко определяет ее красоту относительно s, как количество пар индексов i, j (1 ≤ i ≤ j ≤ n) таких, что подстрока t[i..j] лексикографически больше подстроки s[i..j].

Мальчику стало интересно, сколько существует таких строк t, что их красота относительно s в точности равна k. Помогите ему — найдите остаток от деления этого количества на 1000000007 (10⁹ + 7).

Подстрокой s[i..j] строки s = s₁s₂... s_n будем называть строку s_is_{i  +  1}... s_j.

Строка x  =  x₁x₂... x_p лексикографически больше строки y  =  y₁y₂... y_p, если существует такое число r (r < p), что x₁  =  y₁,  x₂  =  y₂,  ... ,  x_r  =  y_r и x_{r  +  1} > y_{r  +  1}. Символы строк сравниваются как их ASCII коды.