4077 - Ivan and Weighted Fibonacci

Created by Rubén Alcolea Núñez
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Ivan is a high school student who loves math sequences. The first sequence he learned was Fibonacci sequence. He knows that the Fibonacci sequence has two base cases, f[0] = 0 and f[1] = 1, and for all value of n higher than 1, f[n] = f[n-1] + f[n-2]. Thus, the Fibonacci sequence generates the following numbers: {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}.

Last night Ivan created a sequence similar to Fibonacci, that he called Weighted Fibonacci. In this sequence, he kept the same base cases (f[0] = 0 and f[1] = 1) as Fibonacci, but he modified the original sequence a little by adding constants values to weigh the terms involved in the sequence and replacing the second term of Fibonacci with a new one.

In that way, for all values of n greater than 1, f[n] = a * f[n-1] + b * g[n-2] + c, where a, b and c are integer constants. The term g[n] = d * g[n-1] + e * g[n-2] + f, where d, e and f are integer constants. The base cases for g[n] are g[0] = 0 and g[1] = 1. Ivan has asked your help to write a program to compute the value of f[n] for the Weighted Fibonacci sequence.
Ivan es un estudiante de preuniversitario que ama las secuencias matemáticas. La primera secuencia que él aprendió fue la secuencia de Fibonacci. Él sabe que la secuencia de Fibonacci tiene dos casos base, f[0] = 0 y f[1] = 1, y que para todo valor de n mayor que 1, f[n] = f[n-1] + f[n-2]. De este modo, la secuencia de Fibonacci genera los siguientes números: {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}.

Anoche Ivan creó una secuencia similar a Fibonacci, a la que él llamó Fibonacci Ponderado. En esta secuencia, él mantuvo los mismos casos base (f[0] = 0 y f[1] = 1) de Fibonacci, pero modificó un poco la secuencia original al adicionar valores constantes para ponderar los términos de la secuencia y sustituir el segundo término de Fibonacci por uno nuevo.

De esta forma, para todo valor de n mayor que 1, f[n] = a * f[n-1] + b * g[n-2] + c, donde a, b y c son constantes enteras. El término g[n] = d * g[n-1] + e * g[n-2] + f, donde d, e y f son constantes enteras. Los casos bases para g[n] son g[0] = 0 y g[1] = 1. Ivan ha pedido tu ayuda para escribir un programa que calcule el valor de f[n] para la secuencia de Fibonacci Ponderado.
Ivan is a high school student who loves math sequences. The first sequence he learned was Fibonacci sequence. He knows that the Fibonacci sequence has two base cases, f[0] = 0 and f[1] = 1, and for all value of n higher than 1, f[n] = f[n-1] + f[n-2]. Thus, the Fibonacci sequence generates the following numbers: {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}.

Last night Ivan created a sequence similar to Fibonacci, that he called Weighted Fibonacci. In this sequence, he kept the same base cases (f[0] = 0 and f[1] = 1) as Fibonacci, but he modified the original sequence a little by adding constants values to weigh the terms involved in the sequence and replacing the second term of Fibonacci with a new one.

In that way, for all values of n greater than 1, f[n] = a * f[n-1] + b * g[n-2] + c, where a, b and c are integer constants. The term g[n] = d * g[n-1] + e * g[n-2] + f, where d, e and f are integer constants. The base cases for g[n] are g[0] = 0 and g[1] = 1. Ivan has asked your help to write a program to compute the value of f[n] for the Weighted Fibonacci sequence.

Input specification

The input contains in the first line the values of a, b and c (1 ≤ a, b, c ≤ 103), separated by a single space. The second line contains the values of d, e and f (1 ≤ d, e, f ≤ 103), separated by a single space. The third line contains the value 1 ≤ C ≤ 100, representing the number of terms that Ivan wants to compute. The following C lines contain an integer N (1 ≤ N ≤ 109), representing the Nth term to be computed.
La entrada contiene en la primera línea los valores a, b y c (1 ≤ a, b, c ≤ 10^3), separados por un espacio. La segunda línea contiene los valores d, e y f (1 ≤ d, e, f ≤ 10^3), separados por un espacio. La tercera línea contiene el valor 1 ≤ C ≤ 100, que representa el número de términos que Ivan desea calcular. Las siguientes C líneas contienen un entero N (1 ≤ N ≤ 10^9), que representa el n-ésimo término a calcular.
The input contains in the first line the values of a, b and c (1 ≤ a, b, c ≤ 103), separated by a single space. The second line contains the values of d, e and f (1 ≤ d, e, f ≤ 103), separated by a single space. The third line contains the value 1 ≤ C ≤ 100, representing the number of terms that Ivan wants to compute. The following C lines contain an integer N (1 ≤ N ≤ 109), representing the Nth term to be computed.

Output specification

The output has C values, each one in a single line. Each value will be the Nth term of Weighted Fibonacci. The answer for each case can be very large, so print it modulo 1000000007.
La salida tiene C valores, cada uno en una línea. Cada valor será el n-ésimo término del Fibonacci Ponderado. La respuesta en cada caso puede ser muy grande, por lo que se debe imprimir la respuesta módulo 1000000007.
The input contains in the first line the values of a, b and c (1 ≤ a, b, c ≤ 103), separated by a single space. The second line contains the values of d, e and f (1 ≤ d, e, f ≤ 103), separated by a single space. The third line contains the value 1 ≤ C ≤ 100, representing the number of terms that Ivan wants to compute. The following C lines contain an integer N (1 ≤ N ≤ 109), representing the Nth term to be computed.

Sample input

2 2 2
3 4 5
5
1
2
3
4
5

Sample output

1
4
12
42
152

Hint(s)