int fib(int n)
{
    int a, b, p, q;
    a = q = 1;
    b = p = 0;
    while (n > 0)
    {
        if (n % 2 == 0)
        {
            int qq = (q * q) % m;
            q = ((2 * p * q) % m + qq % m) % m;
            p = ((p * p) % m + qq % m) % m;
            n /= 2;
        }
        else
        {
            int aq = (a * q) % m;
            a = ((b * q) % m + aq % m + (a * p) % m) % m;
            b = ((b * p) % m + aq % m) % m;
            n -= 1;
        }
    }
    return b % m;
}