#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;
}