↓これと同じアルゴリズムなのに>>613のは読みにくいね
https://ja.wikipedia.org/wiki/冪剰余#途中で剰余をとる

u64で受け取って内部ではu128で計算して
u64で返すようにしとけばオーバーフローしない