Do you know Fibonacci?

package fibonacci;

import java.util.HashMap;
import java.math.BigInteger;

/*
Do you know Fibonacci?
Flag{last 11617 digits of Fibonacci(336129) module 12345678987654321}
*/

public class Fibonacci {

    private static HashMap<BigInteger, BigInteger> cache = new HashMap<BigInteger, BigInteger>();
    private static BigInteger ONE = BigInteger.ONE;
    private static BigInteger ZERO = BigInteger.ZERO;

    public static void main(String[] args) {
        BigInteger n = new BigInteger("336129");
        BigInteger fn = fibonacci(n);
        BigInteger ten = new BigInteger("10");
        BigInteger tenPow11617 = ten.pow(11617);
        BigInteger last11617 = fn.mod(tenPow11617);
        BigInteger mod = new BigInteger("123456789");
        BigInteger result = last11617.mod(mod);
        System.out.println("Result = " + result);
    }

    // method tim so fibonacci thu n
    public static BigInteger fibonacci(BigInteger n) {
        if (n.equals(ZERO)) {
            return ZERO;
        }
        if (n.equals(ONE)) {
            return ONE;
        }
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        if (n.testBit(0)) {
            BigInteger n2 = n.shiftRight(1);
            BigInteger n3 = n2.add(ONE);
            BigInteger result = fibonacci(n2).multiply(fibonacci(n2)).add(fibonacci(n3).multiply(fibonacci(n3)));
            cache.put(n, result);
            return result;
        } else {
            BigInteger n2 = n.shiftRight(1);
            BigInteger n3 = n2.subtract(ONE);
            BigInteger result = fibonacci(n2).multiply(fibonacci(n2).add(fibonacci(n3).add(fibonacci(n3))));
            cache.put(n, result);
            return result;
        }
    }

}