El otro hijo de Bonacci
Los números de Fibonacci son muy conocidos por los informáticos. La definición recursiva es la siguiente:
f0 = 1
f1 = 1
fn = fn-1 + fn-2
Lo que es menos conocido es que el autor de la recurrencia era en realidad Leonardo de Pisa, al que tras su muerte se le puso el apodo de Fibonacci por ser el hijo (filius) de Bonacci.
La leyenda cuenta que un hermano de Leonardo, harto de la fama que éste había adquirido tras la publicación de su libro Liber Abici intentó también pasar a la posteridad creando una serie de números parecida pero en la que los dos primeros valores no están prefijados:
F0(x,y) = x
F1(x,y) = y
Fn(x,y) = Fn-1(x,y) + Fn-2(x,y)
Con la definición anterior, es claro que fn = Fn(1,1).
La historia puso a cada uno en su lugar y el hermano de Leonardo no consiguió su objetivo (no es fácil superar a la persona que, entre otras cosas, introdujo la numeración arábiga en Europa...), pero intentando recordarle ocho siglos después, queremos calcular algunos de los números de su sucesión.
Entrada
La entrada consta de varios casos de prueba. Cada uno está formado por una línea con tres números, n, x e y (0 ≤ n ≤ 10.000, 0 ≤ x, y ≤ 100.000).
Salida
Para cada caso de prueba se escribirá en una línea independiente el resultado de calcular Fn(x,y) según la definición anterior. Como el resultado puede llegar a ser muy grande, calcularlo módulo 1.000.000.007 (109 + 7).
Entrada de ejemplo
0 5 6 1 3 4 2 9 5 20 99999 100000
Salida de ejemplo
5 4 14 94595812