U464784 七圣召唤 · 武器

旅行者最近迷上了七圣召唤，成天泡在猫尾酒馆，可最近 TA 似乎因为经常输牌而闷闷不乐。

旅行者认为，TA 之所以会输牌是因为每回合的行动费用都难以支持装备十分关键的武器牌。 在七圣召唤中，每回合开始时会有 $n$ 点行动费用，每一点行动费用都有随机的元素类型，一共有 $m$ 种**不同**的元素类型，相同元素类型的费用简称为**相同元素**。 游戏开局时，旅行者天胡地摸到了一张武器牌，这张武器牌需要恰好 $k$ 点相同元素才能装备。为了可以在第二回合杀穿拿下对局，旅行者希望你告诉 TA ，**仅在第一回合**，在所有行动费用的随机结果中，**有多少种不同的结果可以使 TA 成功装备这张武器牌？** 当然，这个结果可能非常大，旅行者只需要对 $10^9+7$ 取模的答案。 **注：两种随机结果不同，当且仅当存在一种元素类型的行动费用数量不一致。** ### 形式化题面 现构造一长度为 $m$ 的非负整数序列 $a$，使得： 1. $a_1+a_2+\dots+a_m=n$； 2. 存在 $1\leq i\leq m$ 使得 $a_i \geq k$。 求合法的序列的个数，对 $10^9+7$ 取模。

一行三个正整数 $n,m,k$。

一行一个正整数表示答案。

### 数据范围（瞎编，因为出题人也不会做） 对于 $20\%$ 的数据，$2\leq n,m,k\leq 6$ ； 对于 $60\%$ 的数据，$2\leq n,m,k\leq 10^2$ ； 对于 $100\%$ 的数据，$2\leq n\leq 2\times 10^5，k\leq n,2\leq m,k\leq 10^3$。