Олег Петрович любит кроссворды и каждый четверг покупает в газетном киоске свой любимый журнал с кроссвордами и разными словесными головоломками. В последнем выпуске Олег Петрович обнаружил интересную головоломку, за решение которой в журнале обещали ценный приз. Ниже мы приводим её формальное описание.

Поле для головоломки состоит из двух рядов по n клеток в каждом. Каждая клетка содержит ровно одну строчную английскую букву. Нужно найти и вычеркнуть на этом поле некоторое данное слово w, состоящее из k строчных английских букв. Решением головоломки является последовательность клеток поля c₁, ..., c_k, такая что:

• Для всех i от 1 до k буква, записанная в клетке c_i, совпадает с буквой w_i;
• Все клетки в последовательности попарно различны;
• Для всех i от 1 до k - 1 клетки c_i и c_i + 1 имеют общую сторону.

Олег Петрович быстро нашёл решение для головоломки. Теперь ему интересно, сколько для нее существует различных решений. Олег Петрович не любит слишком большие числа, поэтому посчитайте ответ по модулю 10⁹ + 7.

Два решения c_i и c'_i считаются различными, если последовательности клеток не совпадают хотя бы в одной позиции, то есть найдётся такое j от 1 до k, что c_j ≠ c'_j.