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

Language	Compilation command
C11	/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o W W.c -lm
C++20	/usr/bin/g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o W W.cpp
C++17	/usr/bin/g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o W W.cpp
Java	/usr/bin/javac -encoding UTF-8 W.java /bin/sh -c echo "Main-Class: W" > __manifest__.txt /bin/sh -c jar cfm W.jar __manifest__.txt *.class
Pypy 3	/usr/bin/pypy3 -m compileall -b W.py /bin/mv W.pyc __main__.pyc /usr/bin/zip W.pyz.zip __main__.pyc /bin/mv W.pyz.zip W.pyz

Time limit	Memory limit	# of submissions	# of submitted users	Solved #	Accepted user ratio
1000 ms	512 MiB	13	6	4	66.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

Problem Source