ZerOne 2

要素からなる数列 であって、以下の条件を全て満たすものの個数を で割ったあまりを求めてください。

• なる全ての整数 に対して、
• なる全ての整数 に対して、 または
• は の倍数

• は整数

条件を満たす数列の個数を で割ったあまりを出力せよ。

3 3

8

、、、、、、、 の 通りが条件を満たします。 は3つ目の条件を満たしますが、2つ目の条件を満たしません。

314 159

971519497

で出力してください。