計算すると
1290148117通り
になりました。
>>72さんの数字と近いけど、微妙に違う。計算間違いか。