Time Limit: 1s
Memory Limit: 128MB
xiaoY is crazy about solving equations! But since teacher HH tells him that when an equation’s degree is bigger than 3, there are no analytic solutions, so he feels very upset! With a few days of trial, he truly trusts his teacher’s words and he focuses on another interesting problem. What is the “Permutation function group” like!
A “Permutation function group” means the coefficient of the function is a permutation of 1 ~N and the format is
F(x) = a1*x^ (1^3) + a2*x^ (2^3) … + an*x^ (N^3);
He is interested about what the F(x) is like when a1...aN form the Kth permutation of all;
As you see, when N=4:
S (1): 1 2 3 4
S (2): 1 2 4 3
S (3): 1 3 2 4
…
S (N) 4 3 2 1
Now give you N, k and x, you just need to tell xiaoY F(x) mod 1000000007 (in case F(x) too large! We module 1000000007)
Multiple cases.
N, K, X (0<N<=1000, 0<K<=3000, x<10^9)
0 0 0 indicates the end of input!
F(x) mod 1000000007
2 2 2 0 0 0
260
2 * 2^(1^3) + 1 * 2^(2^3) = 4 + 256 = 260