inline string mult(string a, string b) {
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	int len1 = a.size(), len2 = b.size();
	int len = len1 + len2;
	int c[len + 10] = {};
	for(int i = 0; i < len1; i++) {
		for(int j = 0; j < len2; j++) {
			c[i + j] += (a[i] - '0') * (b[j] - '0');
		}
	}for(int i = 0; i < len - 1; i++) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}while (c[len] == 0) len --;
	string ans = "";
	for(int i = len; i >= 0; i--) ans += c[i] + '0';
	return ans;
}

inline string fact(int n) {
	string ans = "1";
	for(int i = 1; i <= n; i++) ans = mult(ans, to_string(i));
	return ans;
}

string slowPow(string a, int b) {
    if (b == 0) return "1";
    string res = "1";
    while (b --) {
        res = mult(res, a);
    }return res;
}

string fastPow(string a, int b) {
    string res = "1";
    while (b > 0) {
        if (b & 1) {
            res = mult(res, a);
        }a = mult(a, a);
        b >>= 1;
    }return res;
}

string fastPow(string a, int b) {
    if (b == 0) return "1";
    if (b == 1) return a;

    if (!b & 1) {
        string t = fastPow(a, b >> 1);
        return mult(t, t);
    } else {
        return mult(a, fastPow(a, b - 1));
    }
}