Counting Sequences

题目描述

你的任务是计算长度为 n 的序列的数量，其中每个元素是介于 1 $\dots$ k 之间的整数，并且每个整数 1 $\dots$ k 在序列中至少出现一次。 例如，当 n=6 且 k=4 时，一些合法的序列是 [1,3,1,4,3,2] 和 [2,2,1,3,4,2]。

输入格式

唯一的一行输入包含两个整数 n 和 k。

输出格式

输出一个整数：序列的数量对 10^9+7 取模的结果。

6 4

1560

提示

$1 \le k \le n \le 10^6$

标签: CSES2228|计数问题

来源

CSES2228|计数问题