\(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\)로 나눈 나머지로 출력한다.

riseoj 작성

출처 RiseOJ Basics