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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#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(...) 2137
#endif

template<int M, int R>
struct Mod {
  static const int mod = M, rt = R;
  int x;
  Mod(ll y = 0) : x(y % M) { x += (x < 0) * M; }
  Mod& operator+=(Mod o) {
    if ((x += o.x) >= M) x -= M;
    return *this; }
  Mod& operator-=(Mod o) {
    if ((x -= o.x) < 0) x += M;
    return *this; }
  Mod& operator*=(Mod o) {
    x = 1ll * x * o.x % M;
    return *this; }
  Mod& operator/=(Mod o) { return *this *= o.inv(); }
  friend Mod operator+(Mod a, Mod b) { return a += b; }
  friend Mod operator-(Mod a, Mod b) { return a -= b; }
  friend Mod operator*(Mod a, Mod b) { return a *= b; }
  friend Mod operator/(Mod a, Mod b) { return a /= b; }
  auto operator<=>(const Mod&) const = default;
  Mod pow(ll n) const {
    Mod a = x, b = 1;
    for (; n; n /= 2, a *= a) if (n % 2) b *= a;
    return b; }
  Mod inv() const { assert(x); return pow(M - 2); }
  friend ostream& operator<<(ostream& os, Mod x) {
    return os << x.x; }
};
using mint = Mod<1000000007, 5>;

const int N = 1000100;
int n, m, k;
mint p;
mint f[N], g[N], h[N];

mint policz(int mn) {
  mint lew = 0;
  lew += g[mn - 1] * max(0,min({m, mn + k, k + 1}) - mn) * p;
  int l = max(mn, k + 1);
  int r = min(m, mn + k);
  if (l < r) {
    lew += (r - l) * g[mn - 1] * p;
    int l2 = l - 1 - k - 1;
    int r2 = r - 1 - k - 1;
    lew -= (h[r2] - (l2 >= 0 ? h[l2] : 0)) * p;
  }
  return lew;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> m;
  p = mint(1) / k;
  f[0] = g[0] = h[0] = 1;
  rep(i, 1, N) {
    f[i] = p * (g[i - 1] - (i > k ? g[i - k - 1] : 0));
    g[i] = g[i - 1] + f[i];
    h[i] = h[i - 1] + g[i];
  }
  mint odp = 0;
  // min=0
  mint pot = 1;
  rep(i, 0, n) {
    odp += pot;
    pot *= min(m - 1, k) * p;
  }
  debug(odp);
  // min>0
  rep(mn, 1, m) {
    mint lew = policz(mn);
    mint pra = policz(mn + 1);
    debug(lew, pra);
    if (lew != 0 && pra != 0) {
      mint lewa = lew.pow(n - 1);
      mint iloraz = pra / lew;
      if (iloraz != 1) {
        mint prawa = (1 - iloraz.pow(n)) / (1 - iloraz);
        odp += lewa * prawa * f[mn];
      } else {
        odp += lewa * n * f[mn];
      }
    } else if (lew != 0) {
      odp += lew.pow(n - 1) * f[mn];
    } else if (pra != 0) {
      odp += pra.pow(n - 1) * f[mn];
    }
  }
  cout << odp << '\n';
}