#include<bits/stdc++.h>
using namespace std;

// 快速幂算法，用于计算 (m % z)^y % z
long long powMod(long long m, long long y, long long z) {
    long long res = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            res = (res * m) % z;
        }
        m = (m * m) % z;
        y /= 2;
    }
    return res;
}


int main(){
    string x;
    long long y=0,z=0;
 &n...