倍增法

#include <iostream>
using namespace std;
long long fast_pow(long long a, long long n, long long p) {
    long long res = 1;
    a %= p;
    while(n > 0) {
        if(n & 1) res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}
int main() {
    cout << fast_pow(3, 100, 1000000007) << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005, LOG = 17;
int a[MAXN], st[MAXN][LOG], lg[MAXN];
void build(int n) {
    lg[1] = 0;
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int i=1;i<=n;i++) st[i][0]=a[i];
    for(int j=1;j<LOG;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int query(int L, int R) {
    int k = lg[R-L+1];
    return max(st[L][k], st[R-(1<<k)+1][k]);
}
int main() {
    int n, m; cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    build(n);
    while(m--) {
        int L, R; cin >> L >> R;
        cout << query(L, R) << "\n";
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
const int MAXN=100005, LOG=17;
vector<int> adj[MAXN];
int dep[MAXN], up[MAXN][LOG];
void dfs(int u, int p) {
    up[u][0]=p;
    for(int j=1;j<LOG;j++) up[u][j]=up[up[u][j-1]][j-1];
    for(int v:adj[u]) if(v!=p) { dep[v]=dep[u]+1; dfs(v,u); }
}
int lca(int u, int v) {
    if(dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    for(int j=0;j<LOG;j++) if((d>>j)&1) u=up[u][j];
    if(u==v) return u;
    for(int j=LOG-1;j>=0;j--)
        if(up[u][j]!=up[v][j]) { u=up[u][j]; v=up[v][j]; }
    return up[u][0];
}
int main() {
    int n, m; cin >> n >> m;
    for(int i=0;i<n-1;i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dep[1]=0; dfs(1,1);
    while(m--) {
        int u, v; cin >> u >> v;
        cout << lca(u,v) << "\n";
    }
    return 0;
}

long long dis[MAXN]; // 到根的距离
void dfs(int u, int p, long long d) {
    dis[u] = d; dep[u] = dep[p] + 1;
    up[u][0] = p;
    for(int j=1;j<LOG;j++) up[u][j]=up[up[u][j-1]][j-1];
    for(auto& e : adj[u]) if(e.to != p)
        dfs(e.to, u, d + e.w);
}
// 查询
long long dist(int u, int v) {
    return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
// 预处理
st[i][0] = a[i];
st[i][j] = gcd(st[i][j-1], st[i+(1<<(j-1))][j-1]);
// 查询
int k = lg[R-L+1];
return gcd(st[L][k], st[R-(1<<k)+1][k]);

typedef long long ll;
const ll MOD = 1000000007;
struct Mat { ll m[2][2]; };
Mat mul(Mat A, Mat B) {
    Mat C={{{0,0},{0,0}}};
    for(int i=0;i<2;i++)
      for(int k=0;k<2;k++)
        for(int j=0;j<2;j++)
          C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j])%MOD;
    return C;
}
Mat mpow(Mat A, ll p) {
    Mat R={{{1,0},{0,1}}};
    while(p>0) { if(p&1) R=mul(R,A); A=mul(A,A); p>>=1; }
    return R;
}
int main() {
    ll n; cin >> n;
    if(n<=2) { cout << 1; return 0; }
    Mat T={{{1,1},{1,0}}};
    Mat R = mpow(T, n-2);
    ll ans = (R.m[0][0]*1 + R.m[0][1]*1) % MOD;
    cout << ans << endl;
}