Iterated Linear Function 매트릭스 빠른 멱

Consider a linear function f(x) = Ax + B. Let’s define g(0)(x) = x and g(n)(x) = f(g(n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g(n)(x) modulo 109 + 7.
Input The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — the parameters from the problem statement.
Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.
Output Print the only integer s — the value g(n)(x) modulo 109 + 7.
직접 빠른 멱이면 되는데 갑자기 자신의 블로그에 매트릭스 빠른 멱이 하나도 없다는 것을 발견하고 밀어낸다.[a,b,0,1]^n* [x,0,1,0]
ll과 초기화...각자 한 발씩.괴롭다

#include
#include
#include
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll a, b, n, x;
struct mat {
    ll m[2][2];
};
mat temp = {{1, 0, 0, 1}};
mat muti(mat a, mat b) {
    mat ans;
    memset(ans.m, 0, sizeof(ans.m));
    for(ll i = 0; i < 2; i++) {
        for(ll j = 0; j < 2; j++) {
            ans.m[i][j] = 0;
            for(ll k = 0; k < 2; k++) {
                ans.m[i][j] = (ans.m[i][j] % mod + a.m[i][k] * b.m[k][j] % mod) % mod;
            }
        }
    }
    return ans;
}
mat mquick(ll xxx) {
    mat ans = temp;
    mat temp2 = {{a, b, 0, 1}};
    while(xxx) {
        if(xxx & 1)
            ans = muti(ans, temp2);
        temp2 = muti(temp2, temp2);
        xxx >>= 1;
    }
    return ans;
}
int main() {
    while(~scanf("%lld %lld %lld %lld", &a, &b, &n, &x)) {
        mat fuck = {{x, 0, 1, 0}};
        fuck = muti(mquick(n), fuck);
        printf("%lld
", (fuck.m[0][0] % mod + mod) % mod);
    }
    return 0;
}