1413  Permutation Design
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 214
Solved: 75
 Description
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)
 Input
Multiple cases.
N, K, X (0<N<=1000, 0<K<=3000, x<10^9)
0 0 0 indicates the end of input!
 Output
F(x) mod 1000000007
 sample input

2 2 2 0 0 0
 sample output

260
 hint
2 * 2^(1^3) + 1 * 2^(2^3) = 4 + 256 = 260
 source
 He Jian, HUST Campus 2010, Preliminary