题目描述

你需要设计一个密码 $S$，$S$ 需要满足以下条件：

• $S$ 的长度为 $N$；
• $S$ 只包含小写英文字母；
• $S$ 不包含子串 $T$；

例如：abc 和 abcde 是 abcde 的子串，abdabd 不是 abcdeabcde 的子串。

请问共有多少种不同的密码满足要求？由于答案会非常大，请输出答案模 $10^9 + 7$ 的余数。

输入格式

• 第一行输入整数 $N$，表示密码的长度。
• 第二行输入字符串 $T$，$T$ 中只包含小写字母。

输出格式

输出一个正整数，表示总方案数模 $10^9 + 7$ 后的结果。

数据范围

• $1 \leq N \leq 50$,
• $1 \leq |T| \leq N$，$|T|$ 是 $T$ 的长度。

输入样例1：

2
a

输出样例1：

625

输入样例2：

4
cbc

输出样例2：

456924