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

문제

길이가 N 인 순열이란, 1 이상 N 이하의 자연수 N 개로 이루어진, 같은 수가 두 번 이상 등장하지 않는 수열을 의미한다. 길이가 N 인 순열의 종류는 총 N!개가 있다.

이 순열에서 K-minsum이라는 것을 정의할 것이다. 순열 A 가 있고, 각 원소를 순서대로 나열하면 A1, A2, ..., AN일 때, 순열 A 의 K-minsum은

\[\text{K-minsum}(A) = \sum_{i=1}^{N}{\sum_{j=i+K}^{N}{\text{min}(A_i, A_{i+1}, \cdots, A_{j-1}, A_j)}}\]

이다. min은 인자로 나열된 수 중의 최솟값을 구하는 함수이다. K 가 주어질 때, 길이가 N인 모든 N!개의 순열에 대해 K-minsum을 구해 그 합을 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에는 순열의 길이를 나타내는 자연수 N 과 정수 K(0 ≤ K ≤ N)가 주어진다. (1 ≤ N ≤ 106)

출력

길이가 N 인 모든 N!개의 순열에 대해 K-minsum을 구해 그 합을 출력한다. 합이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력해야 한다.

예제 입력

1 1

예제 출력

0

예제 입력 2

2 0

예제 출력 2

8

예제 입력 3

3 1

예제 출력 3

22

예제 입력 4

5 1

예제 출력 4

1908

예제 입력 5

8 2

예제 출력 5

1435680

예제 입력 6

13 3

예제 출력 6

880193815

힌트

출처

Contest > kriiicon > 제 4회 kriiicon 7번