Coprime Nim はニムゲームであり、「山から取り除く石の個数は、その山の石の個数と互いに素でなければならない」という条件がついている。2人のプレイヤーが交互に石を取り除き、最後の石を取り除いた方が勝ちである。
1 個以上 n-1 個以下の石の山が k 個ある状態のうち、互いに最善手を尽くしたときに先手が負けるものの個数を L(n,k) とする。
例えば L(5,2)=6 である。各山の石の個数が (1,1),(2,2),(2,4),(3,3),(4,2),(4,4) であったときに先手の負けとなる。
L(10,5)=9964, L(10,10)=472400303, L(103, 103) mod 1 000 000 007 = 954021836 である。
L(107, 107) mod 1 000 000 007 を求めよ。