配点: $600$ 点

問題文

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

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

制約

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

入力

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

$K$

$S$

出力

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

5
oof

575111451

たとえば、proofend、moonwolf、onionpuf などが条件を満たします。

それに対し、oofsix、oofelevennn、voxafolt、fooooooo などは条件を満たしません。

37564
whydidyoudesertme

318008117