Медленно работает перемножение матриц java

Добрый день. Написал код, вычисляющий остаток от деления n-ного числа Фибоначчи на вводимое из консоли число, где n может быть очень большим (до 10^18): http://pastebin.com/H9U5q6sr

Использую оптимизированный алгоритм с Q-матрицами: https://habrahabr.ru/post/148336/, возвожу в степень тоже быстро: по алгоритму быстрого возведения в степень. Никаких циклов в вычислении элементов матрицы тоже нет. Работает всё почему-то очень медленно (медленное умножение, как определил). Не понимаю, почему так и как это фиксить. Кто сталкивался-посоветуйте, пожалуйста, как решить проблему.

public void bigfib(){
    Scanner sc = new Scanner(System.in);
    BigInteger n = sc.nextBigInteger();
    BigInteger m = sc.nextBigInteger();
    BigInteger [][] a = new BigInteger[][]{{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
    System.out.println(pow(a,n)[0][1].mod(m));
}
private BigInteger[][] mult(BigInteger[][] m1, BigInteger[][] m2) {
    BigInteger a = m1[0][0];
    BigInteger a2 = m2[0][0];
    BigInteger b = m1[0][1];
    BigInteger b2 =m2[0][1];
    BigInteger c = m1[1][0];
    BigInteger c2 = m2[1][0];
    BigInteger d = m1[1][1];
    BigInteger d2 =m2[1][1];
    BigInteger a11 = a.multiply(a2).add(b.multiply(c2));
    BigInteger a12 = a.multiply(b2).add(b.multiply(d2));
    BigInteger a21 = c.multiply(a2).add(d.multiply(c2));
    BigInteger a22 = c.multiply(b2).add(d.multiply(d2));
    BigInteger[][] mResult = new BigInteger[][]{{a11,a12},{a21,a22}};
    return mResult;
}
private BigInteger[][] pow(BigInteger a[][], BigInteger p) {
    BigInteger my2 = new BigInteger("2");
    BigInteger[][] result;
    if (p.equals(BigInteger.ONE))
        return a;
    if (p.equals(my2))
        return mult(a,a);
    if (p.mod(my2).equals(BigInteger.ONE)) {
        return mult(a,pow(a,p.subtract(BigInteger.ONE)));
    } else {
        result = pow(a,p.divide(my2));
        return mult(result,result);
    }
}