石头游戏

爱丽丝和鲍勃用一些由数组表示的石头堆玩游戏 [a₁,a₂,a₃,...] 其中 a_i 是第 i 堆石子的数量。他们轮流拿石头 爱丽丝 总是先行。在每个回合中，他们必须采取 至少一块石头 最多只能从一堆石头中取出一定数量的石头。游戏开始时，先从第一堆石头中取出石子。如果第一堆空了，他们就可以从第二堆中取出石头。如果第二堆空了，他们就可以从第三堆取石子，以此类推。无法做出有效动作的玩家就输了。

我们定义一个数组[a₁,a₂,a₃,...] 作为获胜配置，如果第一个玩家（爱丽丝）无论第二个玩家（鲍勃）做什么都可以强制获胜，或者如果鲍勃无论爱丽丝做什么都可以强制获胜，则作为失败配置。我们还假设爱丽丝和鲍勃总是玩得很完美。

例如，如果他们轮到最多拿走 2 石子，[2,1] 就是获胜配置。该策略解释如下。
(1) 爱丽丝拿走了第一堆中的一颗石头。
(2) 鲍勃在第一堆中拿走了一颗石头。
(3) 爱丽丝拿走了第二堆中的一颗石头。
(4) 鲍勃无法采取有效的行动，爱丽丝获胜！！！

然而，如果允许他们在一次移动中最多拿走 2 石子，那么 [1,2] 就是一个失败的配置。该策略描述如下。
(1) 爱丽丝拿走了第一堆中的一颗石头。
(2) 鲍勃在第二堆中拿了两颗石头。
(3) Alice 无法做出有效的动作，Alice 输了！！！

我们将函数 $S(K,M,N)$ 定义为获胜配置的数量 [a₁,a₂,a₃,...] 满足以下条件：
(1) 数组中有 $K$ 元素(K 一堆石头）。
(2) $1\le a_i\le M$ 用于 $1\le i\le K$
(3) Alice 和 Bob 一次只能拿走 $N$ 颗棋子。

您获得了 $S(3,4,2)=39$、$S(5,5,3)=2084$ 和 $S(25,25,8)mod1000000007=313496033$
查找$S({10}^{18},{11}^{18},1234567890)mod1000000007$

---

感谢 六广西 将这个问题推广到更大的 K,M,N