1/a が求まれば
あとは乗算2回(と軽い演算)で剰余が求まるでしょ
漸化式にするまでもなく