/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 600 点
問題文
「好きな英小文字 1 文字を好きな位置に挿入する」という操作を文字列 S にちょうど K 回繰り返してできる文字列は何通りあるでしょう？
答えは非常に大きくなる可能性があるので、(10^9+7) で割ったあまりを出力してください。
制約
- K は 1 以上 10^6 以下の整数
- S は英小文字からなる長さ 1 以上 10^6 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
K S
出力
条件を満たす文字列の個数を (10^9+7) で割ったあまりを出力せよ。
入力例 1
5 oof
出力例 1
575111451
たとえば、proofend、moonwolf、onionpuf などが条件を満たします。
それに対し、oofsix、oofelevennn、voxafolt、fooooooo などは条件を満たしません。
入力例 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