#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int n, m, k; long long ans; int pow(int a, int x){ long long result = 1; if(x == 0){ return 0; } while(a > 0){ if(a % 2 == 0){ a = a / 2; x = x * x % mod; } else{ a--; result = result * x % mod; a = a / 2; x = x * x % mod; } } return result % mod; } void dfs(int num, int sum, int cnt){ if(num == k && sum == n){ ans = (ans + cnt) % mod; return; } if(num == k || sum > n){ return; } for(int i = 1; i <= n; i++){ if(sum + i > n){ break; } dfs(num + 1, sum + i, (cnt + pow(m, i)) % mod); } return; } int main(){ cin >> n >> k >> m; dfs(0, 0, 0); cout << ans / 2 << endl; return 0; }