この問題 a^b % 1000000007 を高速に計算するための 繰り返し二乗法（binary exponentiation） の仕組みを 図付きで詳しく解析・説明します。

a と b が与えられたとき、a^b % 1000000007 を 高速に正確に求める。

• a は整数（最大 10^9）→ BigIntで表現
• b は整数（最大 10^18）→ BigIntが必須
• 単純な for ループだと 10^18 回の繰り返しは間に合わない ⟶ よって O(log b) の繰り返し二乗法 を使う

a^b を次のように分解できる：

bが偶数のとき: a^b = (a^(b/2))^2
bが奇数のとき: a^b = a * a^(b-1)

この再帰的な性質を ループで効率的に計算していきます。

→ 3^13 % 1000000007 を計算したい

まず b を2進数に変換：

b = 13 = 1101₂
        ↑ ↑ ↑ ↑
        8 4 0 1  ←（2^3, 2^2, 2^1, 2^0 の位置）

このことから：

3^13 = 3^(8 + 4 + 0 + 1)
     = 3^8 * 3^4 * 3^1

つまり、2進数のビットが1のところだけ掛け算するイメージです。

while (b > 0n) {
    if (b % 2n === 1n) {
        result = (result * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1n;
}

b = 13 = 1101₂
    ↓
[1] b LSB=1 → result *= a        → a = a²
[2] b >>=1 → b=6 (LSB=0)         → a = a²
[3] b >>=1 → b=3 (LSB=1) → *= a  → a = a²
[4] b >>=1 → b=1 (LSB=1) → *= a  → a = a²
終了（b=0）

• b = 123456789012345678 は 10^18 オーバーの巨大整数
• JavaScriptの number は 53bit 精度まで ⟶ BigInt で安全な演算が可能

入力：

123456789 123456789012345678

出力（正解）：

3599437

• 繰り返し二乗法は b を 2進数で分解し、必要なべきだけを掛け合わせる
• O(log b) で非常に高速
• BigInt により超巨大指数にも対応できる
• メモリ使用も極小で、時間・メモリ制約の両方を余裕で満たす