View problem - 접미사 배열의 개수 (kriii3_W)

Time limitMemory limit# of submissions# of submitted usersSolved #Accepted user ratio
1000 ms512 MiB136466.67%

길이가 $N$인 문자열 중에서 문자열을 구성하는 문자의 종류가 $M$가지 이하인 것들의 접미사 배열을 구할 때, 서로 다른 접미사 배열의 개수는 몇 개인가?

입력

첫 번째 줄에 두 자연수 $N$, $M$($1 \le N, M \le 10^{6}$)이 공백으로 구분되어 주어진다.

출력

길이가 $N$인 문자열 중에서 문자열을 구성하는 문자의 종류가 $M$가지 이하인 문자열들의 접미사 배열의 종류의 개수를 $1,000,000,007$로 나눈 나머지를 출력한다.

참고

접미사 배열의 정의는 여기에서 확인할 수 있다.

두 배열 $A$와 $B$가 서로 다르다는 것은, $A[i] \ne B[i]$를 만족하는 정수 $i$가 적어도 하나 존재한다는 것이다.

부분문제

부분문제 점수 N M
1 10 ≤ 103 ≤ 103
2 36 ≤ 106 ≤ 106

입출력 예제

입력

4 2

출력

12
  • [4, 3, 2, 1]: "aaaa", "baaa", "bbaa", "bbba", "bbbb"