Ваше завдання полягає в тому, щоб обчислити кількість рядків довжиною \(n\), які мають заданий шаблон довжини \(m\) як підрядок.

Усі рядки складаються з символів 'A'–'Z'.

Обмеження

• \(1≤n≤1000\)
• \(1≤m≤100\)

Формат вхідних даних

У першому рядку вхідних даних є ціле число \(n\): довжина фінального рядка.

Друга рядок містить шаблон довжиною \(m\).

Формат вихідних даних

Вивести кількість рядків за модулем \(10^9 + 7\).

Пояснення:

Фінальний рядок матиме форму ABCDBx або xABCDB, де x — будь-який символ між 'A'–'Z'.

Приклад вхідних даних

6
ABCDB

Приклад вихідних даних

52