Problem Description

This is a very simple problem. Given three integers N, x, and M, your task is to calculate out the following value:

 

Input

There are several test cases. For each case, there is a line with three integers N, x, and M, where 1 ≤ N, M ≤ 2*10⁹, and 1 ≤ x ≤ 50.
The input ends up with three negative numbers, which should not be processed as a case.

 

Output

For each test case, print a line with an integer indicating the result.

 

Sample Input

 

Sample Output

 

Source

 

 //计算排列数（杨辉三角）

 //C(m,n) = C(m-1,n-1)+C(m-1,n)

 //快速幂

 /*

 *  [题意]

 *   输入n, x, m

 *   求(1^x)*(x^1)+(2^x)*(x^2)+(3^x)*(x^3)+...+(n^x)*(x^n)

 *  [解题方法]

 *   设f[n] = [x^n, n*(x^n), (n^2)*(x^n),..., (n^x)*(x^n)]

 *   则f[n][k] = (n^k)*(x^n)

 *   问题转化为求：( g[n] = f[1][x]+f[2][x]+...+f[n][x] )

 *   设C(i,j)为组合数，即i种元素取j种的方法数

 *   所以有：f[n+1][k] = ((n+1)^k)*(x^(n+1)) （二次多项式展开）

 *                     = x*( C(k,0)*(x^n)  +C(k,1)*n*(x^n)+...+C(k,k)*(n^k)*(x^n) )

 *                     = x*( C(k,0)*f[n][0]+C(k,1)*f[n][1]+...+C(k,k)*f[n][k] )

 *   所以得：

 *   |x*1 0................................0|        |f[n][0]|       |f[n+1][0]|

 *   |x*1 x*1 0............................0|        |f[n][1]|       |f[n+1][1]|

 *   |x*1 x*2 x*1 0........................0|    *   |f[n][2]|   =   |f[n+1][2]|

 *   |......................................|        |.......|       |.........|

 *   |x*1 x*C(k,1) x*C(k,2)...x*C(k,x) 0...0|        |f[n][k]|       |f[n+1][k]|

 *   |......................................|        |.......|       |.........|

 *   |x*1 x*C(x,1) x*C(x,2).......x*C(x,x) 0|        |f[n][x]|       |f[n+1][x]|

 *   |0................................0 1 1|        |g[n-1] |       | g[ n ]  |

 */

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define ll long long

 const ll maxn = ;

 ll c[maxn][maxn];

 ll n, mod, x, m;

 struct Mat{

     ll f[maxn][maxn];

 };

 void init()

 {

     ll i,j,k;

     c[][] = c[][] = c[][] = ;

     for(i = ; i < maxn; i++){

         c[i][] = c[i][i] = ;

         for(j = ; j < i; j++){

             c[i][j] = c[i-][j]+c[i-][j-];

         }

     }

 }

 Mat operator *(Mat a, Mat b)

 {

     ll i, j, k;

     Mat c;

     memset(c.f,,sizeof(c.f));

     for(k = ; k < m; k++){

         for(i = ; i < m; i++){

             for(j = ; j < m; j++){

                 if(!b.f[k][j]) continue;

                 c.f[i][j] = (c.f[i][j]+(a.f[i][k]*b.f[k][j])%mod)%mod;

             }

         }

     }

     return c;

 }

 Mat multi(Mat a,ll b)

 {

     Mat s;

     memset(s.f,,sizeof(s.f));

     for(int i = ; i < m; i++){

         s.f[i][i] = ;

     }

     while(b){

         if(b&) s = s*a;

         a = a*a;

         b>>=;

     }

     return s;

 }

 int main()

 {

     init();

     while(~scanf("%lld%lld%lld",&n,&x,&mod))

     {

         if(n<&&x<&&mod<) break;

         Mat e;

         ll i, j;

         ll ans = ;

         memset(e.f,,sizeof(e.f));

         for(i = ; i <= x; i++){

             for(j = i; j <= x; j++){

                 e.f[j][i] = c[x-i][j-i]*x%mod;

             }

         }

         e.f[][x+] = e.f[x+][x+] = ;

         m = x+;

         e = multi(e,n);

         for(i = ; i < m-; i++) ans = (ans+x*e.f[i][m-])%mod;

         printf("%lld\n",(ans+mod)%mod);

     }

     return ;

 }