Problem 1091 --肥不那几数列

1091: 肥不那几数列

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 439  Solved: 54
[Submit][Status][Web Board][Creator:]

Description

在学习了斐波那契数列 (f1 = f2 = 1, fn = fn−1 + fn−2 , n ≥ 3) 之后,huahua 提出了” 肥不那几数列”: f1 = f2 = 1, fn = A ∗ fn−1 + B ∗ fn−2 , n ≥ 3,其中 A,B 均为常数。 

ZHAN 对这个数列很好奇,学过猪心算的他快速算出了这个数列前 100000 项的每一项,huahua 对 ZHAN 的钞能力很好奇,他想验证一下 ZHAN 算出的数对不对,但他不会写程序,你能帮他写个程序求出这个序列的第 n 项吗? 

由于肥不那几数列增长的速度过快 (关于这点可以输出斐波那数列的前 50 项观察一下),你只需要输出肥不那几数列第 n 项的数值对 1000000007 取模的结果。

Input

输入的第一行包含三个整数 T(1 ≤ T ≤ 1000), A, B(0 ≤ A, B ≤ 100). T 的含义为:对于该数列,huahua 要询问 T 次该数列的第 n 项。 

随后一行,T 个 n(1 ≤ n ≤ 105 ),每个 n 表示询问一次该数列的第 n 项。

Output

对于 huahua 的每一个询问,输出一行一个整数,表示数列的那一项对 1000000007 取模的结果。 

Sample Input

5 1 1
3 5 7 44 45

Sample Output

2
5
13
701408733
134903163

HINT

C/C++ 中取模运算符为%。此外,你需要保证在数列在计算的过程中不会超过该数据类型能表示的最大范围。int 最大值 2147483647,long long 最大值 9223372036854775807。 

Source

[Submit][Status]