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
© 2015 HUST ACMICPC TEAM. All Right Reserved.