Each time there is a sponsor involved, the contest seems to be harder.

This time I struggled a lot on the implementation.

I too faced same problem, not sure what's the issue here (4 test cases were WA)

def mpow(a,b,mod):
    ret=1
    a%=mod
    while b>0:
        if b&1:
            ret=(ret*a)%mod
        a=(a*a)%mod
        b>>=1
    
    return ret

N,K,M = map(int, input().split())
mod=998244353
v1=mpow(K,N, mod-1)

v2=mpow(M,v1, mod)
print(v2%mod)

2 998244352 998244353

The answer should be 0 for this but your code will print 1. Same thing happened with mine then I check if M is multiple of 998244353 answer should be 0

See https://en.wikipedia.org/wiki/Fermat%27s_little_theorem, the second equation is only valid if $$$p \nmid a$$$.

You need to check for $$$998244353 \mid M$$$. If this is $$$0$$$ you must output $$$0$$$.

Might be a stupid question: Is there a lemma or sth, which states how to deal with mod powers? Is this the "general" way of trying to reduce the term via Fermat's Little Theorem? (Like stated in the editorial) My stupid ass thought that just applying modPow would be ok( without -1 in the first mod):

    ll rem = modPow(k, n, mod); // calculating r
    ll ret = modPow(m, rem, mod); // getting the result
    cout << ret;

Use set, you will get accepted.

Initially store all the values from 1 to N in the set and now for every query of type 1 find the lower_bound of x % N. If lower_bound doesn't exists then take the first element because that will be closest to the x. After that set this value to x and erase it from the set.

I used brute force and saw only 2 TLEs. Then I used a hash table to memoize the jump. Only 1 TLE left.
Finally I changed the hash table to a vector. Then I got AC.

we wanna calculate m ^ (k ^ n)

say cnt = k ^ n

now m ^ cnt = m ^ (cnt % (mod — 1)) by fermat's little theorem.

Edit: If you want video explanation u can see my solutions video here

Why we have to add (mod-1) with x in binpow(m, x + mod — 1, mod)?

s!=t