문제 보기 - 접미사 배열의 개수 (kriii3_W)

시간 제한	메모리 제한	제출 횟수	통과한 사람 수	비율
1000 ms	512 MiB	10	4	40.0%

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

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

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

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

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

부분문제	점수	N	M
1	10	≤ 10³	≤ 10³
2	36	≤ 10⁶	≤ 10⁶

입력 예시	출력 예시
`4 2`	`12`

출처

언어	명령
C / gcc	`gcc-10 -Wall -lm -static -DEVAL -o W -O2 W.c`
C++ / g++	`g++-10 -Wall -lm -static -DEVAL -o W -O2 W.cpp`
C++11 / g++	`g++-10 -Wall -lm -static -DEVAL -o W -O2 W.cpp -std=c++11`
C++14 / g++	`g++-10 -Wall -lm -static -DEVAL -o W -O2 W.cpp -std=c++14`
Python 2 / Python 2	`python2.7 -c "import py_compile; py_compile.compile(r'W.py')"`
Python 3 / Python 3	`python3.9 -c "import py_compile; py_compile.compile(r'W.py')"`
PyPy / PyPy 2	`pypy -c "import py_compile; py_compile.compile(r'W.py')"`
C++17 / g++	`g++-10 -Wall -lm -static -DEVAL -o W -O2 W.cpp -std=c++17`
PyPy 3 / PyPy 3	`pypy3 -c "import py_compile; py_compile.compile(r'W.py')"`
Java 11 / Java	`javac -J-Xms128m -J-Xmx512m -encoding UTF-8 W.java`
Kotlin / Kotlin	`kotlinc-jvm -include-runtime -d W.jar W.kt`

접미사 배열의 개수 Batch 컴파일 명령