>>256
x^r-1の剰余を求めるには、係数をr飛びに足し合わせるだけでできますよ。