시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 6 2 2 33.333%

문제

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

입력

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

출력

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

예제 입력

4 2

예제 출력

12

힌트

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

두 배열 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"

 

출처

Contest > kriiicon > 제 3회 kriiicon ㅈ번