>253
(a+b) mod q = ( (a mod q) + (b mod q) ) mod q
(ab) mod q = ( (a mod q) * (b mod q) ) mod q

↑は正しい??これを使えば、桁あふれが防げるってことかな。

最後のfor文って、実際primeの判定には二項分布の係数部分が重要なんだから
直感的にはa=1だけで正しい気がするよね。