private long mul(long a, long b) {
        long result = 0;
        a %= mod;
        b %= mod;
        if (a > b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        while (a != 0) {
            if (a % 2 != 0) {
                result += b;
                if (result >= mod) result -= mod;
                a -= 1;
            }
            a /= 2;
            b += b;
            if (b >= mod) b -= mod;
        }
        System.out.println(result);
        return result;
    }