0,1,…,(108)108+5−1 の番号が付いたボールが 1 つずつあり，いずれもはじめは無色です．ボールの番号 x を 108 進法表記したときの下から k 桁目を f(x,k) とおきます．いくつかのボールに 1024+336 種類の色のうち 1 色を塗ることを考えます．ボールへの着色は以下の操作 i（ i は正整数）により行います．
- 操作 i ：番号 x のボールと整数 j (1≤j≤108+5) および 1024+336 種類の色からまだ使っていない 1 色を選び，f(x,j)=f(y,j) および
f(x,k)≤f(y,k)(k=1,2,…,108+5)
k=1∑108+5(f(y,k)−f(x,k))≤i−1
をいずれも満たす番号 y のボールすべてを選択した色で彩色する．ただし，すでに色が塗られているボールに対しては彩色を行わない．
いま，操作 1 から操作 108 までを適当な順番で 1 回ずつ行ったところ，
k=1∑108+5f(x,k)<108
を満たす番号 x が書かれたボールはすべて何らかの色で彩色されていました．このとき，最終的なボールの彩色のされ方としてあり得るものは M 通りあります．M108+5 を素数 108+7 で割った余りを求めてください．
「108 進法表記したときの下から k 桁目」とは
ボールの番号 x は，0≤f(x,k)<108 をみたす整数 f(x,k) により，
x=k=1∑108+5f(x,k)×(108)k−1
と 108 進法で一意に表示できます．このとき，下から k 桁目は f(x,k) です．