Informatica Online Judge

  교준이의 Secret Code [2303 / 08FF]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 5   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 노규민]

Background

2018년, 윤교준은 NYPC 우승을 차지하고 많은 기자들과 함께 멋진 인터뷰를 진행한다.
평소 그의 행동을 지켜보고 있었던 노규민은 윤교준의 이미지 세탁 능력에 감탄하며, 교준이의 실체를 모두에게 알릴 계획을 세우고 있다.

교준이의 실체를 알리려면 물증이 있어야 하고, 그 물증은 역시 윤교준의 노트북에 있다.
윤교준의 노트북에는 - 다른 대부분의 노트북과 마찬가지로 - 문자열로 되어있는 비밀번호가 있다.

노규민은 이미 다음과 같은 사실을 알고 있다.

사실 1. 윤교준의 노트북은 보안 시스템이 일반적인 노트북과 다르다. 일반적인 노트북은 비밀 문자열를 완벽하게 입력한 후, "엔터"키를 눌러야 노트북을 성공적으로 켤 수 있다.
그러나 윤교준의 노트북은 그렇지 않다. 윤교준이 설정한 비밀 문자열을 $S$라 해보자.
윤교준의 노트북의 보안 시스템은 현재 비밀 문자열 입력란에 $S$를 (연속한) substring으로 가지는 문자열이 입력되었다면, "엔터"키를 누를 필요가 없이 자동으로 잠금을 해제한다.

예시를 들어보자. 윤교준의 비밀 문자열이 "AA"라 하자. 노규민이 비밀 문자열 입력란에 "ABBDEGAA"를 입력하면, 마지막 "A"를 누르자마자 잠금이 해제된다. "AA"라는 substring이 생겼기 때문이다.

사실 2. 윤교준의 비밀 문자열은, 알파벳 대문자로만 이루어져 있고, "A"부터 시작해서 사전순으로 첫 $N$개 알파벳 대문자로만 이루어져 있다. 단, 당연히 $N \le 26$이 성립한다.

노규민은 물증을 얻기 위해 윤교준의 노트북을 훔쳤고, 이제 잠금을 해제하기 위해 다음과 같은 계획을 세웠다.

계획: 첫 $N$개 알파벳 대문자 중 아무거나 동일한 확률로 입력하는 것을, 잠금이 풀릴 시점까지 반복한다.

노트북을 도둑맞고 두려움에 떨고 있는 윤교준은, 노규민이 가지고 있는 $N$의 값과 자신이 설정한 비밀 문자열이 무엇인지 알고 있다.
두려움에 떨고 있는 윤교준을 위해, 노규민이 잠금이 풀릴 때까지 입력해야 하는 문자 수의 기댓값을 구해주자.

이 기댓값은 값이 매우 커질 수 있다. 또한, 이 기댓값이 유리수임을 증명할 수 있다. 그러므로 출력 형식을 다음과 같이 한다.

기댓값이 $\frac{P}{Q}$라면, (단, $\text{gcd}(P, Q)=1$이다) 합동식 $Qx \equiv P$ $mod (10^9+7)$의 근 $x$를 출력한다.
단, $0 \le x < 10^9 +7$이다. 이러한 근 $x$는 유일하게 존재함이 보장된다.

Input

첫째 줄에 $N$의 값이 주어진다. ($1 \le N \le 26$)
둘째 줄에는 윤교준의 비밀 문자열의 길이 $L$이 주어진다. ($1 \le L \le 250000$)
둘째 줄에 윤교준의 비밀 문자열 $S$가 주어진다.

Output

잠금이 풀릴 때까지 입력해야 하는 문자 수의 기댓값을 문제에서 제시한 형식으로 출력한다.

IO Example

입력 예시 1
1
2
AA

출력 예시 1
2

입력 예시 2
5
1
A

출력 예시 2
5

입력 예시 3
2
2
AA

출력 예시 3
6

입력 예시 4
2
5
AABAB

출력 예시 4
32

예제 입출력은 Test Case에 포함되어 있지 않다. 즉, 예제는 채점하지 않는다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]