题目描述

「好きな英小文字 $1$ 文字を好きな位置に挿入する」という操作を文字列 $S$ にちょうど $K$ 回繰り返してできる文字列は何通りあるでしょう？

答えは非常に大きくなる可能性があるので、$(10^9+7)$ で割ったあまりを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$K$ $S$

输出格式

条件を満たす文字列の個数を $(10^9+7)$ で割ったあまりを出力せよ。

题目大意

对于字符串 $S$ ,进行 $K$ 次下列操作可以变成多少个不同的字符串。

• 向任意位置插入一个小写英文字符。

答案可能很大，输出答案 $\bmod 10 ^ 9 +7$ 。 by djh123456 。

5
oof

575111451

37564
whydidyoudesertme

318008117

提示

制約

• $K$ は $1$ 以上 $10^6$ 以下の整数
• $S$ は英小文字からなる長さ $1$ 以上 $10^6$ 以下の文字列

Sample Explanation 1

たとえば、proofend、moonwolf、onionpuf などが条件を満たします。 それに対し、oofsix、oofelevennn、voxafolt、fooooooo などは条件を満たしません。