You are given four positive integers x0, x1, a, b. And you know xi=a⋅x(i−1)+b⋅x(i−2) for all i≥2.

Given two positive integers n, and MOD, please calculate x_nx
n modulo MOD.
Does the problem look simple? Surprise! The value of n may have many many digits!
输入描述:
The input contains two lines.
The first line contains four integers x0, x1, a, b(1≤x0 ,x1,a,b≤10^9).
The second line contains two integers n, MOD (1≤n<10(10^6)),10^9 < MO D≤ 2×10^9, n has no leading zero).
输出描述:
Print one integer representing the answer.
示例1
输入
复制
1 1 1 1
10 1000000001
输出
复制
89
说明
The resulting sequence x is Fibonacci sequence. The 11-th item is 89.
示例2
输入
复制
1315 521 20185 5452831
9999999999999999999999999999999999999 1000000007
输出
复制
914730061
题意：
给你一个递推式：
f[2] = x0
f[1] = x1
f[n] = a * f[n - 1] + b * f[n - 2] (i >= 2)
给出：x0, x1, a, b, mod
求f[n]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
typedef long long ll;
ll mod;
char str[maxn];
const int mlen = 2;
struct Matrix {
    ll a[mlen][mlen];
    Matrix() {
        MatrixInit();
    }
    void MatrixDiag() {
        MatrixInit();
        for (int i = 0; i < mlen; i++) a[i][i] = 1;
    }
    void MatrixInit() {
        for (int i = 0; i < mlen; i++) 
            for (int j = 0; j < mlen; j++) a[i][j] = 0;
    }
    Matrix MatrixMul(Matrix b) {
        Matrix c;
        for (int i = 0; i < mlen; i++) {
            for (int j = 0; j < mlen; j++) {
                for (int k = 0; k < mlen; k++) {
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return c;
    }
    Matrix MatrixPow(ll n) {
        Matrix ans; ans.MatrixDiag();
        Matrix b = *this;
        while (n) {
            if (n & 1) ans = ans.MatrixMul(b);
            b = b.MatrixMul(b);
            n >>= 1;
        }
        return ans;
    }
};
int main() {
    ll x0, x1, a, b;
    scanf("%lld%lld%lld%lld", &x0, &x1, &a, &b);
    scanf("%s%lld", str + 1, &mod);
    Matrix res, ans;
    res.a[0][0] = a; res.a[0][1] = b; res.a[1][0] = 1; res.a[1][1] = 0;
    ans.MatrixDiag();
    int len = strlen(str + 1);
    for (int i = len; i >= 1; i--) { //十进制求法
        int p = str[i] - '0';
        if (p) {
            Matrix tmp = res.MatrixPow(p);
            ans = ans.MatrixMul(tmp);
        }
        res = res.MatrixPow(10);
    }
    printf("%lld\n", (ans.a[1][0] * x1 + ans.a[1][1] * x0) % mod);
    return 0;
}