# Mathematician QSC

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 208    Accepted Submission(s): 101

Problem Description
QSC dream of becoming a mathematician, he believes that everything in this world has a mathematical law.

Through unremitting efforts, one day he finally found the QSC sequence, it is a very magical sequence, can be calculated by a series of calculations to predict the results of a course of a semester of a student.

This sequence is such like that, first of all,f(0)=0,f(1)=1,f(n)=f(n2)+2f(n1)(n2)Then the definition of the QSC sequence is g(n)=ni=0f(i)2. If we know the birthday of the student is n, the year at the beginning of the semester is y, the course number x and the course total score s, then the forecast mark is xg(ny)%(s+1).
QSC sequence published caused a sensation, after a number of students to find out the results of the prediction is very accurate, the shortcoming is the complex calculation. As clever as you are, can you write a program to predict the mark?

Input
First line is an integer T(1≤T≤1000).

The next T lines were given n, y, x, s, respectively.

n、x is 8 bits decimal integer, for example, 00001234.

y is 4 bits decimal integer, for example, 1234.
n、x、y are not negetive.

1≤s≤100000000

Output
For each test case the output is only one integer number ans in a line.

Sample Input
2
20160830 2016 12345678 666
20101010 2014 03030303 333

Sample Output
1
317

1定是1个 22 的矩阵，然后在根据 f(n) 的递推式得到 A 矩阵中的具体值，算出来是：
0112

xg(xy)%Phi(s+1)+Phi(s+1)%(s+1)(1) ，否则只能暴力计算，然后我们发现只有当 ny11 的时候才暴力计算也很简单了，直接求，

f(i)f(i+1) 有关系，那末 f(i)f(i+1) 等于甚么呢：

f

------分隔线----------------------------

------分隔线----------------------------

15粉丝
7关注