1044 - 数论：矩阵快速幂：广义斐波那契数列升级版1
Time Limit : 1 秒
Memory Limit : 256 MB
f(n)=a * f(n-1)+b * f(n-2)+c；（a,b,c是常数）
其中f(1)=1，f(2)=3,求当n接近30亿时，f(n)和10007求模后的值。
Input
输入n,a,b,c四个整数 a,b,c<=10^9，n接近30亿
Output
输出1个整数
Examples
Input
3 1 1 1
Output
5