GitHub 源文件 Markdown 中文

A Certain Unscientific Sum of Falling Factorials and Binomial Coefficients¶

Indicative time limit: 0.5 seconds. Memory limit: 128 MiB. Recalibrate as twice the slowest standard median in the target environment, rounded up to 0.5 seconds. See the environment.

Story¶

While working through the paper for Academy City's Zeroth High School Mock Exam, Xiao A came across an interesting mathematics problem and decided to use his knowledge of algorithms to expand its input bounds.

Formal Problem Statement¶

Given positive integers \(n,k\) , define the falling factorial

\[ i^{\underline{k}}=i(i-1)\cdots(i-k+1) \]

If \(i<k\) , this product contains a zero factor and is zero. Compute

\[ \sum_{i=1}^{n}i^{\underline{k}}\binom ni\pmod P,\qquad P=10^9+7 \]

Here \(\binom ni\) counts subsets of \(i\) distinct objects chosen from \(n\) . Both object labels and the order of display positions distinguish arrangements.

Input Format¶

One line containing n k .

Output Format¶

Print one line containing the residue in \([0,P-1]\) .

Sample 1¶

Input¶

3 2

Output¶

Sample 2¶

Input¶

2 3

Output¶

Sample 3¶

Input¶

5 5

Output¶

Constraints and Scoring¶

\(1\le n,k\le10^9\) . In particular, \(n<P\) , but \(k\) may exceed \(n\) .

Score	Additional constraints
100%	None

There are 10 formal files worth 10% each. See the test recipes.