【題解】Codeforces GYM 102644B. String Mood

#include <iostream>
using namespace std;
 
long long n, mod = 1e9+7, a[2][2], ans[2];
 
int main() {
    cin >> n;
    ans[0] = 1;
    a[0][0] = 19;
    a[0][1] = 6;
    a[1][0] = 7;
    a[1][1] = 20;
    while (n){
        if (n & 1){
            long long tmp[2] = {};
            for (int i = 0; i < 2; i++){
                for (int k = 0; k < 2; k++){
                    tmp[i] += a[i][k]*ans[k];
                    tmp[i] %= mod;
                }
            }
            for (int i = 0; i < 2; i++){
                ans[i] = tmp[i];
            }
        }
        long long tmp[2][2] = {};
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 2; k++){
                    tmp[i][j] += a[i][k]*a[k][j];
                    tmp[i][j] %= mod;
                }
            }
        }
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                a[i][j] = tmp[i][j];
            }
        }
        n >>= 1;
    }
    cout << ans[0] << "\n";
}