레이팅 미적용설명
\(n\)개 원소 집합에서 \(k\)개 원소 집합으로 가는 전사함수(위로의 함수)의 수를 \(10^9+7\)로 나눈 나머지로 세시오. 포함–배제에 의해 이는 \(\sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n\)이다. \(k>n\)이면 답은 \(0\)이다.
제약
입력 형식
한 줄에 두 정수 \(n\)과 \(k\)가 주어진다 (\(1 \le n \le 10^6\), \(1 \le k \le 2000\)).
출력 형식
전사함수의 수를 \(10^9+7\)로 나눈 나머지로 출력한다.
예제 1
입력
3 2
출력
6
예제 2
입력
4 3
출력
36
예제 3
입력
2 5
출력
0
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그