Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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(n-2)+2*f(n-1)(n\geq 2)$Then the definition of the QSC sequence is $g(n)=\sum_{i=0}^{n}f(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 $x^{g(n*y)}\%(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?

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(n-2)+2*f(n-1)(n\geq 2)$Then the definition of the QSC sequence is $g(n)=\sum_{i=0}^{n}f(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 $x^{g(n*y)}\%(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?

提交代码