El cálculo de Fibonacci en Java Longs se muestra negativo

Mi calculadora Fibonacci funciona bien, pero al subir a números más altos, el resultado es negativo, como lo haría si fuera unInteger por encima de su valor máximo.

Está trabajando con un cachéjava.util.Map<Integer, Long>. Todo lo que entra en elMap es exactamente lo que se espera, pero al imprimirlo me sale p. para 291:

-784134397488903422

De acuerdo ahttp://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibCalcX.html, debería ser:

2923602405716568564338475449381171413803636207598822186175234

Parece que algo va mal con miLongs, pero aún no estoy seguro, qué exactamente. ¿Podría alguien señalarme en la dirección correcta?

Valores de laMap entradas:http://pastebin.com/uje07Ays