#include <bits/stdc++.h> using namespace std; const int mod = 1000000007; int n, m, k; //int fi[5005]; int fw[5005]; int fpow(int x, int y) { int ans = 1; while (y) { if (y & 1) { ans = 1ll * ans * x % mod; } x = 1ll * x * x % mod; y >>= 1; } return ans; } map<pair<pair<int, int>, int>, pair<int, int> > mp; pair<int, int> dfs(int x, int h, int s) { if (mp.find(make_pair(make_pair(x, h), s)) != mp.end()) return mp[make_pair(make_pair(x, h), s)]; if (x == 1) { if (h < s) return mp[make_pair(make_pair(x, h), s)] = make_pair(0, 0); // fi[h]++; return mp[make_pair(make_pair(x, h), s)] = make_pair(fw[h], 1); } int ans = 0, cnt = 0; for (int i = s; i <= h; i++) { if (i * x > h) break; pair<int, int> dg = dfs(x - 1, h - i, i); // cout << dg.first << " " << dg.second << endl; ans = (1ll * ans + dg.first + fw[i]) % mod; // fi[i] += dg.second; cnt += dg.second; } return mp[make_pair(make_pair(x, h), s)] = make_pair(ans, cnt); } int main() { //freopen("math.in", "r", stdin); //freopen("math.ans", "w", stdout); scanf("%d%d%d", &n, &k, &m); for (int i = 1; i <= n; i++) { fw[i] = fpow(i, m); } auto ans = dfs(k, n, 1); printf("%d %d\n", ans.first, ans.second); // for (int i = 1; i <= n; i++) { // printf("%d ", fi[i]); // } // for (int i = 1; i <= 10; i++) { // for (int j = 1; j <= i; j++) // printf("%d ", fi[i]); // } }