记录编号	611367	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[THUPC 2025 Final] 喜爱之钥	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	4.195 s
提交时间	2026-01-28 23:16:16	内存使用	1.67 MiB

#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 1000000007
#define MAXN 54
#define MAXL 5004
#define MAXK 54
int e[MAXN], p[2][MAXK][MAXN], inv[2 * MAXL + MAXK];  
inline void _update(int * const a, const int lbd, const int rbd, const int base, const int diff) {
  (a[0] += base) %= MOD;
  (a[lbd] += diff) %= MOD;
  (a[rbd] += MOD - diff) %= MOD;
  return ;
}
#define Hill(_a, _lbd, _rbd, _base, _diff) _update(_a, _lbd, _rbd, _base, _diff)
#define Valley(_a, _lbd, _rbd, _base, _diff) _update(_a, _rbd, _lbd, ((_base) + (_diff)) % MOD, MOD - (_diff))
#define Update(_a, _lbd, _rbd, _base, _diff) { if (_lbd < _rbd) Hill(_a, _lbd, _rbd, _base, _diff); else Valley(_a, _lbd, _rbd, _base, _diff); }
int main() {
  freopen("thupc_2025_key.in", "r", stdin);
  freopen("thupc_2025_key.out", "w", stdout);
  int n, l, k, i, j, a, b, d, dh, now, nxt, totk, ntry, prob, pd, pb, lbd, rbd;
  scanf("%d %d %d", &n, &l, &k);
  if (n == 1) {
    printf("%d\n", l);
    return 0;
  }
  inv[1] = 1;
  j = 2 * l + k;
  for (i = 2; i <= j; ++i) inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
  
  p[0][0][0] = 1;
  p[0][0][1] = -1;
  now = 0; nxt = 1;
  for (i = 0; i < l; ++i) {
    for (j = 0; j <= k; ++j) {
      totk = l + k - i - j;
      for (a = 1; a < n; ++a) (p[now][j][a] += p[now][j][a - 1]) %= MOD;
      for (a = 0; a < n; ++a) {
        // Match at the first try
        prob = 1ll * p[now][j][a] * inv[totk] % MOD;
        // fprintf(stderr, "%d %d %d: P = %d\n", i, j, a, prob);
        (e[a] += prob) %= MOD;
        if (a != n - 1) (e[a + 1] += MOD - prob) %= MOD;
        (p[nxt][j][(a + 1) % n] += prob) %= MOD;
        if (a != n - 2) (p[nxt][j][(a + 2) % n] += MOD - prob) %= MOD;

        prob = 1ll * prob * inv[totk + l - i - 2] % MOD;
        // Same lock
        pd = 1ll * prob * (ntry = totk - 1) % MOD;
        pb = 1ll * (ntry / n) * pd % MOD;
        if (dh = ntry % n) {
          // (pd += pb) %= MOD;
          // fprintf(stderr, "+[1, %d]: high %d\n, +(%d, n]: low %d\n", dh, pd, dh, pb);
          lbd = (a + 1) % n;
          rbd = (a + dh) % n + 1; 
          Update(e, lbd, rbd, pb, pd);
          (++lbd) %= n;
          ++(rbd  %= n); 
          Update(p[nxt][j], lbd, rbd, pb, pd);
        }
        else {
          // fprintf(stderr, "+[1, %d]: high %d\n, +(%d, n]: low %d\n", dh, pd, dh, pb);
          (e[0] += pb) %= MOD;
          (p[nxt][j][0] += pb) %= MOD;
        }

        // Same key
        pd = 1ll * prob * (ntry = l - i - 1) % MOD;
        if (j < k) {
          pb = 1ll * pd * (k - j) % MOD; 
          b = (a + l - i) % n;
          (p[now][j + 1][b] += pb) %= MOD;
          if (b != n - 1) (p[now][j + 1][b + 1] += MOD - pb) %= MOD;
        }
        pb = 1ll * (ntry / n) * pd % MOD;
        if (dh = ntry % n) {
          // (pd += pb) %= MOD;
          // fprintf(stderr, "+[1, %d]: high %d\n, +(%d, n]: low %d\n", dh, pd, dh, pb);
          lbd = (a + 1) % n;
          rbd = (a + dh) % n + 1; 
          Update(e, lbd, rbd, pb, pd);
          (++lbd) %= n;
          ++(rbd  %= n); 
          Update(p[nxt][j], lbd, rbd, pb, pd);
        }
        else {
          // fprintf(stderr, "+[1, %d]: high %d\n, +(%d, n]: low %d\n", dh, pd, dh, pb);
          (e[0] += pb) %= MOD;
          (p[nxt][j][0] += pb) %= MOD;
        }
      }
    }

    now ^= 1;
    nxt ^= 1;
    memset(p[nxt], 0, sizeof(int) * MAXK * MAXN);
  }
  for (i = 1; i < n; ++i) (e[i] += e[i - 1]) %= MOD;

  for (i = 0; i < n; ++i) printf("%d%c", e[i], " \n"[i == n - 1]);
  return 0;
}