T515077 [APC001] G - Gifts

# 十分抱歉本题出锅，请正在思考本题的选手无视本题。 旅行者，欢迎来到纳塔！  图片来源自《原神》 5.0 版本壁纸，版权属于 miHoyo，侵权请联系出题人删除。

火神大人想要请你参加「五百年纳塔拯救计划」。但她想先确认一下你的实力。在刚刚结束的「归火圣夜巡礼」中，有很多人落榜。但火神大人决定给他们发一些纪念品以示激励。 火神大人的手上有 $n$ 种不同的礼物，每种礼物均可以视为有无限个。 由于参赛选手们都希望自己收到的 $m$ 个礼物是独特的，所以火神大人不仅需要保证任意一个参赛选手收到的礼物均不相同，还需要保证任意两个参赛选手收到的礼物中相同种类的礼物不能超过 $k$ 个，否则他们就会生气。 现在火神大人想问你最多可以满足多少个参赛选手的要求呢？ 由于参赛选手可能非常多，你只需要求出其对 $10007$ 取模后的结果。

无

无

对于 $100\%$ 的数据，$1\le k< m \le n \le 10^{18}$。