#include <bits/stdc++.h>
using namespace std;
 
// Cách 1: Nhị phân lũy thừa 
long long power_iterative(long long a, long long n, long long m) {
    long long res = 1;
    a %= m;
 
    while (n > 0) {
        if (n & 1) {             // Nếu bit cuối của n là 1 (n lẻ)
            res = (res * a) % m; // Nhân cơ số a hiện tại vào kết quả
        }
        a = (a * a) % m;         // Bình phương cơ số a
        n >>= 1;                 // Dịch phải 1 bit (chia đôi n)
    }
 
    return res;
}
 
// Cách 2: Đệ quy
long long power_recursive(long long a, long long n, long long m) {
    if (n == 0) return 1 % m;
 
    a %= m;
    long long half = power_recursive(a, n / 2, m); // Tính a^(n/2)
    long long half_sq = (half * half) % m;          
 
    if (n % 2 == 1) { // Nếu n lẻ: a^n = a * (a^(n/2))^2
        return (half_sq * a) % m;
    } else {          // Nếu n chẵn: a^n = (a^(n/2))^2
        return half_sq;
    }
}
 
int main() {
    long long a = 3;
    long long n = 13;
    long long m = 1e9 + 7;
 
    cout << power_iterative(a, n, m) << "\n" << power_recursive(a, n, m); // Output: 1594323
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBDw6FjaCAxOiBOaOG7iyBwaMOibiBsxal5IHRo4burYSAKbG9uZyBsb25nIHBvd2VyX2l0ZXJhdGl2ZShsb25nIGxvbmcgYSwgbG9uZyBsb25nIG4sIGxvbmcgbG9uZyBtKSB7CiAgICBsb25nIGxvbmcgcmVzID0gMTsKICAgIGEgJT0gbTsKICAgIAogICAgd2hpbGUgKG4gPiAwKSB7CiAgICAgICAgaWYgKG4gJiAxKSB7ICAgICAgICAgICAgIC8vIE7hur91IGJpdCBjdeG7kWkgY+G7p2EgbiBsw6AgMSAobiBs4bq7KQogICAgICAgICAgICByZXMgPSAocmVzICogYSkgJSBtOyAvLyBOaMOibiBjxqEgc+G7kSBhIGhp4buHbiB04bqhaSB2w6BvIGvhur90IHF14bqjCiAgICAgICAgfQogICAgICAgIGEgPSAoYSAqIGEpICUgbTsgICAgICAgICAvLyBCw6xuaCBwaMawxqFuZyBjxqEgc+G7kSBhCiAgICAgICAgbiA+Pj0gMTsgICAgICAgICAgICAgICAgIC8vIEThu4tjaCBwaOG6o2kgMSBiaXQgKGNoaWEgxJHDtGkgbikKICAgIH0KICAgIAogICAgcmV0dXJuIHJlczsKfQoKLy8gQ8OhY2ggMjogxJDhu4cgcXV5CmxvbmcgbG9uZyBwb3dlcl9yZWN1cnNpdmUobG9uZyBsb25nIGEsIGxvbmcgbG9uZyBuLCBsb25nIGxvbmcgbSkgewogICAgaWYgKG4gPT0gMCkgcmV0dXJuIDEgJSBtOwogICAgCiAgICBhICU9IG07CiAgICBsb25nIGxvbmcgaGFsZiA9IHBvd2VyX3JlY3Vyc2l2ZShhLCBuIC8gMiwgbSk7IC8vIFTDrW5oIGFeKG4vMikKICAgIGxvbmcgbG9uZyBoYWxmX3NxID0gKGhhbGYgKiBoYWxmKSAlIG07ICAgICAgICAgIAogICAgCiAgICBpZiAobiAlIDIgPT0gMSkgeyAvLyBO4bq/dSBuIGzhurs6IGFebiA9IGEgKiAoYV4obi8yKSleMgogICAgICAgIHJldHVybiAoaGFsZl9zcSAqIGEpICUgbTsKICAgIH0gZWxzZSB7ICAgICAgICAgIC8vIE7hur91IG4gY2jhurVuOiBhXm4gPSAoYV4obi8yKSleMgogICAgICAgIHJldHVybiBoYWxmX3NxOwogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGxvbmcgbG9uZyBhID0gMzsKICAgIGxvbmcgbG9uZyBuID0gMTM7CiAgICBsb25nIGxvbmcgbSA9IDFlOSArIDc7CgogICAgY291dCA8PCBwb3dlcl9pdGVyYXRpdmUoYSwgbiwgbSkgPDwgIlxuIiA8PCBwb3dlcl9yZWN1cnNpdmUoYSwgbiwgbSk7IC8vIE91dHB1dDogMTU5NDMyMwogICAgcmV0dXJuIDA7Cn0=