[ECNU] EOJ Monthly 2021.9 Sponsored by TuSimple A. Amazing Discovery

https://acm.ecnu.edu.cn/contest/448/problem/A/

#include 
using namespace std;
typedef long long ll;
ll a, b, n;
const int mod = 998244353;
namespace nekko {
struct owo {
    ll a, k;
    // a + ksqrt b -> (a+ksb)*(A+Ksb)= aA+kKb+(aK+kA)sb
} I = { 1, 0 };
owo mul(owo a, owo b) {
    return (owo) { (a.a * b.a % mod + a.k * b.k % mod * :: b % mod) % mod, (a.a * b.k % mod + a.k * b.a % mod) % mod };
}

owo pw(owo a, ll b) {
    owo res = I;
    for( ; b ; b >>= 1, a = mul(a, a)) {
        if(b & 1) {
            res = mul(res, a);
        }
    }
    return res;
}
void main() {
    cin >> a >> b >> n;
    owo p = (owo) {a, 1}; p = mul(p, p); p = mul(p, I);
    ll S = pw((owo) {a, 1}, n).a + pw((owo) {a, -1}, n).a;
    cout << (S % mod + mod) % mod << endl;
}
}

int main() {
    nekko :: main();
}