1413 - Permutation Design

Time Limit: 1s Memory Limit: 128MB

Submissions: 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