int add(int a, int b, int mod) {
    return ((a % mod) + (b % mod)) % mod;
}
 
int mul(int a, int b, int mod) {
    return ((a % mod) * (b % mod)) % mod;
}
 
int sub(int a, int b, int mod) {
    return ((a % mod) - (b % mod) + mod) % mod;
}
 
int GCD(int a, int b) {
    return b == 0 ? a : GCD(b, a % b);
}
 
int LCM(int a, int b) {
    return a / GCD(a, b) * b;
}
 
int fast_power_recursive(int b, int p) {
    if (!p)
        return 1;
    int r = fast_power_recursive(b, p / 2);
    r *= r;
    if (p & 1)
        r *= b;
    return r;
}
 
int fast_power_iterative(int a, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1)
            ret *= a;
        a = a * a;
        b /= 2;
    }
    return ret;
}

aW50IGFkZChpbnQgYSwgaW50IGIsIGludCBtb2QpIHsKICAgIHJldHVybiAoKGEgJSBtb2QpICsgKGIgJSBtb2QpKSAlIG1vZDsKfQoKaW50IG11bChpbnQgYSwgaW50IGIsIGludCBtb2QpIHsKICAgIHJldHVybiAoKGEgJSBtb2QpICogKGIgJSBtb2QpKSAlIG1vZDsKfQoKaW50IHN1YihpbnQgYSwgaW50IGIsIGludCBtb2QpIHsKICAgIHJldHVybiAoKGEgJSBtb2QpIC0gKGIgJSBtb2QpICsgbW9kKSAlIG1vZDsKfQoKaW50IEdDRChpbnQgYSwgaW50IGIpIHsKICAgIHJldHVybiBiID09IDAgPyBhIDogR0NEKGIsIGEgJSBiKTsKfQoKaW50IExDTShpbnQgYSwgaW50IGIpIHsKICAgIHJldHVybiBhIC8gR0NEKGEsIGIpICogYjsKfQoKaW50IGZhc3RfcG93ZXJfcmVjdXJzaXZlKGludCBiLCBpbnQgcCkgewogICAgaWYgKCFwKQogICAgICAgIHJldHVybiAxOwogICAgaW50IHIgPSBmYXN0X3Bvd2VyX3JlY3Vyc2l2ZShiLCBwIC8gMik7CiAgICByICo9IHI7CiAgICBpZiAocCAmIDEpCiAgICAgICAgciAqPSBiOwogICAgcmV0dXJuIHI7Cn0KCmludCBmYXN0X3Bvd2VyX2l0ZXJhdGl2ZShpbnQgYSwgaW50IGIpIHsKICAgIGludCByZXQgPSAxOwogICAgd2hpbGUgKGIgPiAwKSB7CiAgICAgICAgaWYgKGIgJiAxKQogICAgICAgICAgICByZXQgKj0gYTsKICAgICAgICBhID0gYSAqIGE7CiAgICAgICAgYiAvPSAyOwogICAgfQogICAgcmV0dXJuIHJldDsKfQ==