1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;

const long long MOD=1000000007;

long long power(long long base, long long exp) 
{
    long long res=1;

    base%=MOD;

    while(exp>0) 
    {
        if(exp%2==1) 
        {
            res=(res*base)%MOD;
        }

        base=(base*base)%MOD;
        exp/=2;
    }

    return res;
}

long long inverse(long long n) 
{
    return power(n,MOD-2);
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long n,k,m;
    cin>>n>>k>>m;

    vector<long long> q(m);
    vector<long long> sq(m+1,0);
    vector<long long> sjq(m+1,0);

    q[0]=1;
    sq[1]=1;
    sjq[1]=0;
    
    long long inv=inverse(k);

    for(int s=1; s<m; s++) 
    {
        int left=max(0,s-(int)k);
        long long sum=(sq[s]-sq[left]+MOD)%MOD;
    
        q[s]=(sum*inv)%MOD;
        sq[s+1]=(sq[s]+q[s])%MOD;
        sjq[s+1]=(sjq[s]+(long long)s*q[s])%MOD;
    }

    long long total=0;
    
    for(int s=0; s<m; s++) 
    {
        long long ws=0;
    
        if(s==0) 
        {
            ws=1; 
        } 
        else 
        {
            int mk=(int)m-(int)k-1;
            int l=max(0,s-(int)k);
            int r=s-1;
            
            int mid=min(r,mk);

            if(l<=mid) 
            {
                long long sum=(sq[mid+1]-sq[l]+MOD)%MOD;
                long long jq=(sjq[mid+1]-sjq[l]+MOD)%MOD;
                long long term=(k-s+1+MOD)%MOD;
            
                ws=(ws+term*sum%MOD+jq)%MOD;
            }
            
            if(max(l,mid+1)<=r) 
            {
                long long start=max(l,mid+1);
                long long sum=(sq[r+1]-sq[start]+MOD)%MOD;
            
                ws=(ws+(m-s+MOD)%MOD*sum)%MOD;
            }
            
            ws=(ws*inv)%MOD;
        }

        long long hs=(k-min(k,m-s-1)+MOD)%MOD*inv%MOD;
        long long term;

        if(hs==0) 
        {
            term=n%MOD*q[s]%MOD*power(ws,n-1)%MOD;
        } 
        else 
        {
            long long val1=power(ws,n);
            long long inner=(ws-q[s]*hs%MOD+MOD)%MOD;
            long long val2=power(inner,n);

            term=(val1-val2+MOD)%MOD*inverse(hs)%MOD;
        }

        total=(total+term)%MOD;
    }

    cout<<total<<endl;

    return 0;
}