11393번 - 접미사 배열의 개수

문제

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

입력

첫 번째 줄에 두 자연수 N, M(1 ≤ N, M ≤ 10⁶)이 공백으로 구분되어 주어진다.

출력

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

제한

힌트

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

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

• [1, 2, 3, 4]: "aaab"
• [1, 2, 4, 3]: "aabb"
• [1, 4, 3, 2]: "abbb"
• [2, 3, 4, 1]: "baab"
• [2, 4, 1, 3]: "babb"
• [3, 1, 4, 2]: "abab"
• [3, 4, 2, 1]: "bbab"
• [4, 1, 2, 3]: "aaba"
• [4, 1, 3, 2]: "abba"
• [4, 2, 3, 1]: "baba"
• [4, 3, 1, 2]: "abaa"
• [4, 3, 2, 1]: "aaaa", "baaa", "bbaa", "bbba", "bbbb"