java - Solution for Modular Fibonacci works for small integers but not for big ones -

i'm working in solution problem 10229 of uva (modular fibonacci) , code works small integers big inputs (n = 2.147.483.647, exemple) program seems stuck. checked see if methods multi , pot creating infinite loop neither multi nor pot seem problem. input n = 21474836647 , m = 4, multi has 49 calls , pot has 31 calls right. so, problem be?

import java.math.biginteger; import java.math.bigdecimal; import java.util.scanner;   class main {     class matrix {         biginteger[] values;          public matrix(biginteger a, biginteger b, biginteger c, biginteger d) {             values = new biginteger[4];             values[0] = a;             values[1] = b;             values[2] = c;             values[3] = d;         }          public matrix multi(matrix m1, matrix m2) {             matrix result;             biginteger[] p = new biginteger[7];             biginteger[] q = new biginteger[4];              //strassen algorithm             p[0] = m1.values[0].multiply(m2.values[1].subtract(m2.values[3]));             p[1] = m2.values[3].multiply(m1.values[0].add(m1.values[1]));             p[2] = m2.values[0].multiply(m1.values[2].add(m1.values[3]));             p[3] = m1.values[3].multiply(m2.values[2].subtract(m2.values[0]));             p[4] = (m1.values[0].add(m1.values[3])).multiply(m2.values[0].add(m2.values[3]));             p[5] = (m1.values[1].subtract(m1.values[3])).multiply(m2.values[2].add(m2.values[3]));             p[6] = (m1.values[0].subtract(m1.values[2])).multiply(m2.values[0].add(m2.values[1]));              q[0] = ((p[4].add(p[3])).subtract(p[1])).add(p[5]);             q[1] = p[0].add(p[1]);             q[2] = p[2].add(p[3]);             q[3] = ((p[4].add(p[0])).subtract(p[2])).subtract(p[6]);              result = new matrix(q[0], q[1], q[2], q[3]);              return result;         }          public matrix pot(matrix m1, int n) {             matrix x;              // exponentiation squaring (for matrices)             if (n == 0) {                 return new matrix(biginteger.one, biginteger.zero, biginteger.zero, biginteger.one);              } else if (n == 1) {                 return m1;              } else {                 x = pot(m1, n/2);                  if (n % 2 == 0) {                     return multi(x, x);                  } else {                     return multi(multi(m1, x), x);                 }              }         }     }      public static void main(string args[]) {         matrix inicial, atual;         int n, m;         biginteger m, power;         scanner in = new scanner(system.in);         inicial = new matrix(biginteger.one, biginteger.one, biginteger.one, biginteger.zero);          while (in.hasnextline()) {             n = in.nextint();             m = in.nextint();               atual = matrix.pot(inicial, n);             power = new bigdecimal(math.pow(2, m)).tobiginteger();             m = atual.values[1].mod(power);              system.out.println(m);         }     } } 

i don't think it's stuck. think takes long time. took code , added few lines determine running time.

    long start = system.nanotime();     atual = matrix.pot(inicial, n);     power = new bigdecimal(math.pow(2, m)).tobiginteger();     m = atual.values[1].mod(power);     long end = system.nanotime();     long runns = (end - start);     double runs = ((double)runns)/1000000000.0;      system.out.println(m);     system.out.println(runs); 

running 10,000,000 (ten million) , 4, takes 4.3 seconds. running twenty million , 4, takes 11.8 seconds. fifty million , 4 took 38 seconds. running 2,147,483,647? take long time. several hours @ least.