/*
Author:Chieh
Because Of Coding
*/
//dp[i]=dp[i-1]*m-s;s=dp[i-1]-s; 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct matrix
{
   LL e[2][2];
};
matrix Cal(matrix p,matrix q,int len,int MOD)
{
    matrix c;
    for(int i=0; i<len; i++)
    {
        for(int j=0; j<len; j++)
        {
            c.e[i][j]=0;
            for(int k=0; k<len; k++)
            {
                c.e[i][j]=(c.e[i][j]+((p.e[i][k]*q.e[k][j])%MOD))%MOD;
            }
        }
    }
    return c;
}
const int MOD=1000000007;
int n,m,k;
matrix a,s;
void init()
{
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            if(i==j)s.e[i][j]=1;
            else s.e[i][j]=0;
        }
    }
    a.e[0][0]=m;
    a.e[0][1]=1;
    a.e[1][0]=-k;
    a.e[1][1]=-1;
}
void exp_pow(int b)
{
    while(b)
    {
        if(b&1)s=Cal(s,a,2,MOD);
        a=Cal(a,a,2,MOD);
        b>>=1;
    }
}
void play()
{
    exp_pow(n);
    LL ans=s.e[0][0];
    while(ans<0)ans+=MOD;
    printf("%lld\n",ans);

}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234567;
int k,M;
int  m[maxn][2];
int f[maxn];
int C[71][31];
void init()
{
    m[0][0]=C[0][M];
    m[0][1]=C[0][M];
    m[1][0]=C[1][M];
    m[1][1]=C[0][M];
    f[1]=C[1][M];
    m[2][0]=C[1][M];
    m[2][1]=C[1][M];
    f[2]=C[2][M];
    for(int i=3; i<=k; i++)
    {
        m[i][0]=C[m[i-1][0]+m[i-1][1]][M];
        m[i][1]=f[i-1];
        f[i]=m[i-2][1];
        f[i]=C[f[i]+C[m[i-2][0]*2][M]][M];
    }
}
void play()
{
    printf("%d\n",(m[k][0]+m[k][1]+f[k])%M);
}
int main()
{
    for(int i=0; i<=70; i++)
    {
        for(int j=1; j<=30; j++)
        {
            C[i][j]=i%j;
        }
    }
    while(scanf("%d%d",&k,&M)!=EOF)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}
/*
Author:Chieh
Because Of Coding
*/
// dp[i]=dp[i-1]+dp[i-3]+dp[i-4]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct matrix
{
    int e[4][4];
 
};
matrix Cal(matrix p,matrix q,int len,int MOD)
{
    matrix c;
    for(int i=0; i<len; i++)
    {
        for(int j=0; j<len; j++)
        {
            c.e[i][j]=0;
            for(int k=0; k<len; k++)
            {
                c.e[i][j]=(c.e[i][j]+(p.e[i][k]*q.e[k][j]%MOD))%MOD;
            }
        }
    }
    return c;
}
int M;
int k;
matrix s,a;
void init()
{
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(i==j)s.e[i][j]=1;
            else s.e[i][j]=0;
            if(i!=1&&j==0)a.e[i][j]=1;
            else if(i+1==j)a.e[i][j]=1;
            else a.e[i][j]=0;
        }
    }
}
void exp_pow(int b)
{
    while(b){
        if(b&1)s=Cal(s,a,4,M);
        a=Cal(a,a,4,M);
        b>>=1;
    }
}
int ai[4];
void play()
{
    if(k<=4)printf("%d\n",ai[k-1]%M);
    else{
        k=k-4;
        exp_pow(k);
        int ans=0;
        for(int i=0;i<4;i++){
            ans=(ans+((ai[3-i]*s.e[i][0])%M))%M;
        }
        printf("%d\n",ans);
    }
}
int main()
{
    ai[0]=2;
    ai[1]=4;
    ai[2]=6;
    ai[3]=9;
    while(scanf("%d%d",&k,&M)!=EOF)
    {
 
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
int k,m;
int F[10];
int d;
struct matrix
{
    LL e[10][10];
};
void init()
{
    d=9;
    for(int i=0; i<=9; i++)
    {
        scanf("%d",&F[i]);
    }
}
matrix mul(matrix p,matrix q)
{
    LL i,j,k;
    matrix c;
    for(i=0; i<=d; i++)
    {
        for(j=0; j<=d; j++)
        {
            c.e[i][j]=0;
            for(k=0; k<=d; k++)
                c.e[i][j]=(c.e[i][j]+p.e[i][k]*q.e[k][j])%m;
        }
    }
    return c;
}
matrix s;
matrix a;
void matrix_pow(LL b)
{
    while(b)
    {
        if(b&1)s=mul(s,a);
        a=mul(a,a);
        b=b>>1;
    }
    //a矩阵的b次 返回 s矩阵
}

void play()
{
    if(k<10)printf("%d\n",k);
    else
    {
        for(int i=0; i<=9; i++)
        {
            for(int j=0; j<=9; j++)
            {
                if(i==j) s.e[i][j]=1;
                else s.e[i][j]=0;
            }
        }
        // cout<<s.e[0][2]<<endl;

        for(int i=0; i<=9; i++)
        {
            for(int j=0; j<=9; j++)
            {
                if(j==0)
                {
                    a.e[i][j]=F[i];
                }
                else if(i+1==j)
                {
                    a.e[i][j]=1;
                }
                else
                {
                    a.e[i][j]=0;
                }
            }
        }
        /*   for(int i=0; i<=9; i++)
           {
               for(int j=0; j<=9; j++)
               {
                   cout<<a.e[i][j]<<" ";
               }
               cout<<endl;
           }
           cout<<"---------------------------"<<endl;*/
        matrix_pow(k-9);
        /*  for(int i=0; i<=9; i++)
          {
              for(int j=0; j<=9; j++)
              {
                  cout<<s.e[i][j]<<" ";
              }
              cout<<endl;
          }*/
        LL ans=0;
        int t=9;
        for(int i=0; i<=9; i++)
        {
            ans=(ans+(t*s.e[i][0])%m)%m;
            t--;
        }
        printf("%I64d\n",ans);
    }
}
int main()
{
    while(scanf("%d%d",&k,&m)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
int len[100000];
int Link[11];
int idx[11];
int  Get(int x,int y)
{

    while(1)
    {
        int ys=x%10;
        x/=10;
        y--;
        if(y==0)return ys;
    }
}
void init()
{

    Link[1]=1;
    int p=2;
    for(int i=2; i<=10; i++)
    {
        Link[i]=Link[i-1]+p;
        p*=2;
        p*=2;
    }
    int st=1;
    int bef=0;
    for(int i=1; i<=99999; i++)
    {
        int t;
        if(i>=10000)t=5;
        else if(i>=1000)t=4;
        else if(i>=100)t=3;
        else if(i>=10)t=2;
        else t=1;
        int now=bef+t;
        if(st<=10&&now>=Link[st])
        {
            int xi=Link[st]-bef;
            idx[st]=Get(i,t-xi+1);
            st++;
        }
        len[i]=idx[st-1];
        bef=now;
    }
}
int n;
void play()
{
    printf("%d\n",len[n]);
}
int main()
{
    init();
    while(scanf("%d",&n)!=EOF){
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=3*123456;
int ai[maxn];
int n,k;
bool cmp(int a,int b)
{
    return a>b;
}
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
    sort(ai+1,ai+1+n,cmp);
}
LL dp[5678][5678];
void play()
{
    if(n%k==0)
    {
        LL sum=0;
        int p=n/k;
        for(int i=1; i<=n; i+=p)
        {
            sum+=ai[i]-ai[i+p-1];
        }
        printf("%I64d\n",sum);
    }
    else
    {

        int ys=n%k;
        int s1=ys;
        int v1=n/k+1;
        int s2=k-ys;
        int v2=n/k;
        for(int i=0; i<=k; i++)
        {
            for(int j=0; j<=k; j++)
            {
                dp[i][j]=1000000000000000000LL;
            }
        }
        dp[0][0]=0;
        for(int i=0;i<=s1;i++){
            for(int j=0;j<=s2;j++){
               int a1=i;
               int a2=j;
               int st=i*v1+j*v2+1;
                if(a1<s1){
                    dp[a1+1][a2]=min(dp[a1+1][a2],dp[a1][a2]+ai[st]-ai[st+v1-1]);
                }
                if(a2<s2){
                    dp[a1][a2+1]=min(dp[a1][a2+1],dp[a1][a2]+ai[st]-ai[st+v2-1]);
                }
            }
        }
        printf("%I64d\n",dp[s1][s2]);
    }
}


int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=5*12;
double  ai[maxn*maxn][maxn][maxn];
int T,n,m;
double ans;
void init()
{
    ans=0;
    scanf("%d%d",&n,&m);
    ai[0][0][0]=1;
    double  p=n*m;
    for(int k=1; k<=n*m; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                ai[k][i][j]=0;
                ai[k][i][j]+=i*j*ai[k-1][i-1][j]/p;
                ai[k][i][j]+=j*i*ai[k-1][i][j-1]/p;
                ai[k][i][j]+=i*j*ai[k-1][i-1][j-1]/p;
                if((i!=n||j!=m)&&i*j>=k)
                {
                    ai[k][i][j]+=ai[k-1][i][j]*(i*j-k+1)/p;
                }
            }
        }
        p--;
    }
}
void play()
{

    double ans=0;
    for(int i=1; i<=n*m; i++)
    {
        ans+=ai[i][n][m]*i;
    }
    printf("%.10f\n",ans);
}

int main()
{

    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define INF 1e-9
using namespace std;
const int maxn=1234;
int n;
double ai[maxn][maxn];
double bi[maxn][maxn*2];
double ans[maxn];
void init()
{
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    ai[0][0]=1;
    for(int i=1; i<=2*1000; i++)
    {
        //w
        for(int j=1; j<=i; j++)
        {
            int w=j;
            int b=i-j;
            if(w<=1000&&b<1000)
            {
                ai[w][b]+=(ai[w-1][b]/2.0);
                if(w>b)
                bi[w][w+b]+=(ai[w-1][b]/2.0);
            }
        }
        //b
        for(int j=1; j<=i; j++)
        {
            int w=i-j;
            int b=j;
            if(b<=1000&&w<1000)
            {
                ai[w][b]+=(ai[w][b-1]/2.0);
                if(b>w)
                bi[b][w+b]+=(ai[w][b-1]/2.0);
            }
        }
    }

    for(int i=1; i<=1000; i++)
    {
        double tm=0;
        for(int j=0; j<=i*2; j++)
        {
            tm+=bi[i][j]*j;
        }
        ans[i]=tm;
    }

}

void play()
{
    scanf("%d",&n);
    printf("%.2f\n",ans[n]);


}
int T;
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {

        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define INF 1e-9
using namespace std;
const int maxn=1234;
int n;
double ai[maxn][maxn];
double ans[maxn];
void init()
{
    memset(ai,0,sizeof(ai));
    for(int i=0; i<=1000; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            int w=i;
            int b=j;
            if(w==0&&b==0)ai[i][j]=1;
            else
            {
                if(w!=0)
                {
                    ai[w][b]+=(ai[w-1][b]/2.0);
                }
                if(b!=0)
                {
                    ai[w][b]+=(ai[w][b-1]/2.0);
                }
                if(w>b)
                {
                    ans[w]+=(ai[w-1][b]/2.0)*(w+b);
                }
                if(b>w)
                {
                    ans[b]+=(ai[w][b-1]/2.0)*(w+b);
                }
            }
        }
    }
}

void play()
{
    scanf("%d",&n);
    printf("%.2f\n",ans[n]);


}
int T;
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {

        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=123;
//bool isC[maxn][maxn];
vector<int> V[maxn];
int n,E;
void init(){
    for(int i=1;i<=100;i++)V[i].clear();
    int u,v;
  //  memset(isC,0,sizeof(isC));
    for(int i=1;i<=n;i++){
        scanf("%d%d",&u,&v);
        if(u==v)continue;
        V[u].push_back(v);
     //   isC[u][v]=1;
    }
    /*for(int k=1;k<=100;k++){
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++){
                if(isC[i][k]&&isC[k][j])isC[i][j]=1;
            }
        }
    }*/
    scanf("%d",&E);
}
bool flag;
bool vis[maxn];
void DFS(int now){
    if(flag)return;
    for(int i=0;i<V[now].size();i++){
        int v=V[now][i];
        if(vis[v]){
            flag=1;
            return;
        }
        vis[v]=1;
        DFS(v);
        vis[v]=0;
    }
}
void play(){
    flag=0;
    memset(vis,0,sizeof(vis));
    vis[E]=0;
    DFS(E);
    if(flag)printf("No\n");
    else printf("Yes\n");
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        if(n<0)break;
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=3*12345;
struct he
{
    int l,r;
    LL lazy;
    LL sum;
} Sky[maxn*4];
void BuildTree(int l,int r,int now)
{
    Sky[now].l=l;
    Sky[now].r=r;
    Sky[now].lazy=0;
    Sky[now].sum=0;
    if(l==r)return;
    int mid=(l+r)/2;
    BuildTree(l,mid,now*2);
    BuildTree(mid+1,r,now*2+1);
}
void Push(int now)
{
    if(Sky[now].lazy==0)return;
    int nl=Sky[now].l;
    int nr=Sky[now].r;
    if(nl==nr)return;
    LL v=Sky[now].lazy;
    int mid=(nl+nr)/2;
    Sky[now*2].lazy=v;
    Sky[now*2].sum=v*(mid-nl+1);
    Sky[now*2+1].lazy=v;
    Sky[now*2+1].sum=v*(nr-mid);
    Sky[now].lazy=0;
}
void Update(int l,int r,int now,LL val)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {
        Sky[now].lazy=val;
        Sky[now].sum=val*(r-l+1);
        return;
    }
    int mid=(Sky[now].l+Sky[now].r)/2;
    if(r<=mid)
    {
        Update(l,r,now*2,val);
    }
    else if(l>mid)
    {
        Update(l,r,now*2+1,val);
    }
    else
    {
        Update(l,mid,now*2,val);
        Update(mid+1,r,now*2+1,val);
    }
    Sky[now].sum=Sky[now*2].sum+Sky[now*2+1].sum;

}
LL Query(int l,int r,int now)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {

        return Sky[now].sum;
    }
    int mid=(Sky[now].l+Sky[now].r)/2;
    LL o1=0;
    LL o2=0;
    Push(now);
    if(r<=mid)
    {
        o1=Query(l,r,now*2);
    }
    else if(l>mid)
    {
        o2=Query(l,r,now*2+1);
    }
    else
    {
        o1=Query(l,mid,now*2);
        o2=Query(mid+1,r,now*2+1);
    }
    return o1+o2;

}
int n,m;
LL Calc(LL val, int dn, bool isok)
{
    if(val>=0){
        int p=val/dn;
        if(isok)return p+1;
        else return p;
    }
    else{
        int p=val/dn;
        if(isok)return p;
        else return p-1;
    }
}

void init()
{
    BuildTree(1,n,1);
    int t;
    LL sum=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&t);
        Update(i,i,1,t);
        sum+=t;
    }
    int l,r;
    while(m--)
    {
        scanf("%d%d",&l,&r);
        if(l>r)swap(l,r);
        LL p=Query(l,r,1);
        int len=(r-l+1);
        if(p%len==0)
        {
            Update(l,r,1,p/len);
        }
        else
        {
            if(Sky[1].sum<=sum)
            {
            Update(l,r,1,Calc(p,r-l+1,1));
            }
            else
            {
                Update(l,r,1,Calc(p,r-l+1,0));
            }
        }
    }
}

void play()
{
    bool first=1;
    for(int i=1; i<=n; i++)
    {
        LL p=Query(i,i,1);
        if(!first)printf(" ");
        first=0;
        printf("%lld",p);
    }
    printf("\n");
    printf("\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=8*12345;
bool isP[maxn];
int n;
const int MOD=1000000007;
LL ai[2][maxn];
LL sum[maxn];
int bi[maxn];
int E;
void init()
{
    memset(isP,0,sizeof(isP));
    isP[1]=1;
    for(int i=2; i<=80000; i++)
    {
        if(isP[i])continue;
        for(int j=i+i; j<=80000; j+=i)
        {
            isP[j]=1;
        }
    }

    E=0;
    for(int i=1; i<=80000; i++)
    {
        if(isP[i])
        {
            isP[i]=0;
            continue;
        }
        isP[i]=1;
        E++;
        bi[E]=i;
    }

    memset(ai,0,sizeof(ai));
    for(int i=1; i<=E; i++)
    {
        for(int j=i; j<=E; j++)
        {
            LL t1=bi[i];
            LL t2=bi[j];

            if(t1+t2<=80000)
            {
                ai[0][t1+t2]=(ai[0][t1+t2]+1);
            }
            if(t1*t2<=80000)
            {
                ai[1][t1*t2]=(ai[1][t1*t2]+1);
            }
        }
    }
}
int k;
void play()
{
    sum[k]=0;
    sum[k]+=isP[k];
    LL p=(ai[0][k]+ai[1][k]);
    sum[k]=(sum[k]+p)%MOD;
    LL n1=0;
    LL n2=0;
    for(int i=1; i<=E; i++)
    {
        if(bi[i]>=k)break;
        int t=k-bi[i];
        if(t%2==0)
        {
            int q=t/2;
            if(q==bi[i])
            {
                n1+=2;
            }
            else n1+=isP[q];
        }
        n1=(n1+ai[0][t]);
        n2=(n2+ai[1][t]);
        int q=k%bi[i];
        if(q==0)
        {
            t=k/bi[i];
            int q=sqrt(t);
            if(q*q==t)
            {
                if(q==bi[i])
                {
                    n1+=2;
                }
                else n1+=isP[q];
            }
            n1=(n1+ai[1][t]);
        }
    }
    n1=n1/3;
    sum[k]=(sum[k]+n1);
    sum[k]=(sum[k]+n2);
    printf("%lld\n",sum[k]);
}
int main()
{
    init();
    while(scanf("%d",&k)!=EOF)
    {
        play();
    }
    return 0;
}