F - Strivore /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600

問題文

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

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

制約

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

入力

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

K
S

出力

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


入力例 1

5
oof

出力例 1

575111451

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

それに対し、oofsixoofelevennnvoxafoltfooooooo などは条件を満たしません。


入力例 2

37564
whydidyoudesertme

出力例 2

318008117

Score: 600 points

Problem Statement

How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?

The answer can be enormous, so print it modulo (10^9+7).

Constraints

  • K is an integer between 1 and 10^6 (inclusive).
  • S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

K
S

Output

Print the number of strings satisfying the condition, modulo (10^9+7).


Sample Input 1

5
oof

Sample Output 1

575111451

For example, we can obtain proofend, moonwolf, and onionpuf, while we cannot obtain oofsix, oofelevennn, voxafolt, or fooooooo.


Sample Input 2

37564
whydidyoudesertme

Sample Output 2

318008117