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
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
    o << "{";
    for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
    return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
    return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) {}
#endif

#define x first
#define y second
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define rep(i, a, b) for (ll i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)((x).size()))

using ll = long long;
using pii = pair<ll, ll>;

template <int MOD>
struct Modular {
  int value;
  static const int MOD_value = MOD;

  Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

  Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
  friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
  friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};

using mint = Modular<ll(1e9)+7>;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, K, M; cin >> N >> K >> M;
  // #define mint (long double)
  vec<mint> dp(M);
  vec<mint> pref(M+1);
  vec<mint> qpref(M+1);
  dp[0] = pref[0] = 1;
  rep (m, 1, M) {
    dp[m] = (pref[m-1] - (m-1-K<0 ? 0 : pref[m-1-K]))/mint(K);
    pref[m] = pref[m-1] + dp[m];
    qpref[m] = qpref[m-1] + m*dp[m];
  }

  auto get = [](const vec<mint>& v, int i) {
    if (i < 0 || i >= v.size()) {
      return mint(0);
    }
    return v[i];
  };

  auto ask = [&](int l, int r) {
    if (l > r) return mint(0);
    // assuming coefficient next to l should be 1
    mint k = r-l+1; // coeff next to r
    mint A = k-r;
    return (get(qpref, r) - get(qpref, l-1)) + A * (get(pref, r) - get(pref, l-1));
  };

  mint total = 0;
  mint coef = 1/mint(K);
  rep (m, 0, M) {
    mint e = max(0ll, m+K-M+1)/mint(K);
    mint p = dp[m];
    mint q = (ask(m-K+1, m-1) - ask(M-K, m-1)) * coef;
    debug(e*2, p*2, q*2);
    mint add = 0;
    if (e == 0) {
      add = p * N; 
      debug(add*2);
    } else {
      add = (mexp(p + q, N) - mexp(p * (1 - e) + q, N))/e;
      debug(add*2);
    }
    total += add;
  }
  debug(total);
  cout << total << "\n";
  return 0;
}