插入字母

题目描述

对字符串 $S$ 恰好重复 $K$ 次「在任意位置插入 $1$ 个喜欢的英文字母小写」这个操作,可以得到多少种字符串?

由于答案可能非常大,请输出除以 $(10^9+7)$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$K$
$S$

输出格式

输出满足条件的字符串个数除以 $(10^9+7)$ 的余数。

样例

5
oof

575111451

例如,proofend、moonwolf、onionpuf 等满足条件。

与之相对,oofsix、oofelevennn、voxafolt、fooooooo 等不满足条件。

37564
whydidyoudesertme

318008117

数据范围

• $K$ 是 $1$ 以上 $10^6$ 以下的整数
• $S$ 是由英文字母小写组成、长度为 $1$ 以上 $10^6$ 以下的字符串