Stone game

Alice and Bob play a game with some piles of stones denoted by an array [a₁,a₂,a₃,...] where a_i is the number of stones in the i-th pile. They take stones by turns and Alice always goes first. In each turn they must take at least one stone and at most a certain number of stones from a single pile. The game begins with taking stones from the first pile. If the first pile becomes empty, they are permitted to take stones from the second pile. If the second pile becomes empty, they are permitted to take stones from the third pile, and so on. The player who can not make a valid move loses.

We define an array [a₁,a₂,a₃,...] as the winning configuration if the first player(Alice) can force a win no matter what the second player(Bob) does, or the losing configuration if Bob can force a win no matter what Alice does. We also assume that Alice and Bob always play perfectly.

For example, [2,1] is a winning configuration if they can take at most 2 stones in his/her turn. The strategy is explained below.
(1) Alice takes one stone in the first pile.
(2) Bob takes one stone in the first pile.
(3) Alice takes one stone in the second pile.
(4) Bob can not make a valid move, Alice wins!!!

However, [1,2] is a losing configuration if they are allowed to take at most 2 stones in a single move. The strategy is described below.
(1) Alice takes one stone in the first pile.
(2) Bob takes two stones in the second pile.
(3) Alice can not make a valid move, Alice loses!!!

We define the function $S(K,M,N)$ as the number of winning configurations [a₁,a₂,a₃,...] that satisfy the following conditions:
(1) There are $K$ elements in the array(K piles of stones).
(2) $1\le a_i\le M$ for $1\le i\le K$
(3) Alice and Bob can take no more than $N$ stones in a single move.

You are given $S(3,4,2)=39$, $S(5,5,3)=2084$, and $S(25,25,8)mod1000000007=313496033$
Find $S({10}^{18},{11}^{18},1234567890)mod1000000007$

---

Thanks to liuguangxi for promoting this problem to larger K,M,N