本人是数竞党，看到题目表示非常低血压，但看到题解都在预处理杨辉三角血压又高起来了

kummer定理，lucas定理是非常有用的工具，在处理这种问题的时候注意将k的每一个质因子部分（如12拆成4*3）都完成此操作，（lucas定理在此题中可能没法使用），即可简洁地解决此问题。

具体定理内容和证明可以百度搜索，到时候我把代码写完可以发上来

（还是说kummer定理实际上很费时间复杂度？）