long long multi(long long a, long long b, long long mod)
{
    if (!b) return 0LL;
    long long T = multi(a, b / 2, mod) % mod;
    return ((((T + T) % mod) + ((b & 1) ? (a % mod) : 0LL)) % mod);
}
                                            _Zadkiel