Задача Кактусы

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class cacti_as implements Runnable {
    final long MOD = 1000000007;

    final long INV2 = BigInteger.valueOf(2).modInverse(BigInteger.valueOf(MOD)).longValue();

    public void solve() throws IOException {
        Scanner in = new Scanner(new File("cacti.in"));
        PrintWriter out = new PrintWriter("cacti.out");

        int n = in.nextInt();

        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1]) * i % MOD;
        }

        long[][] c = new long[n + 1][n + 1];
        c[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
            }
        }

        long[] a = new long[n + 1];
        long[] ah = new long[n + 1];
        a[0] = ah[0] = 1;
        a[1] = ah[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int k = 1; k <= i - 1; k++) {
                ah[i] = (ah[i] + (k * c[i - 2][k - 1] % MOD * a[k] % MOD * ah[i - k]) % MOD) % MOD;
            }

            for (int l = 3; l <= i; l++) {
                long[][] d = new long[l][i - l + 1];
                for (int k = 0; k <= i - l; k++) {
                    d[0][k] = (c[i - 1][k] * ah[k + 1]) % MOD;
                }
                for (int j = 1; j < l; j++) {
                    for (int k = 0; k <= i - l; k++) {
                        for (int t = 0; t <= k; t++) {
                            d[j][k] = (d[j][k] + d[j - 1][k - t] * c[i - j - k + t][t + 1] % MOD * ah[t + 1] % MOD * (t + 1) % MOD) % MOD;
                        }
                    }
                }
                a[i] = (a[i] + d[l - 1][i - l] * INV2) % MOD;
            }

            a[i] = (a[i] + ah[i]) % MOD;

//            System.out.println(a[i]);
        }
        out.println(a[n]);

        long[] b = new long[n + 1];
        long[] bh = new long[n + 1];
        b[0] = bh[0] = 1;
        b[1] = bh[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int k = 1; k <= i - 1; k++) {
                bh[i] = (bh[i] + (k * c[i - 2][k - 1] % MOD * b[k] % MOD * b[i - k]) % MOD) % MOD;
            }

            for (int l = 3; l <= i; l++) {
                long[][] d = new long[l][i - l + 1];
                for (int k = 0; k <= i - l; k++) {
                    d[0][k] = (c[i - 2][k] * b[k + 1]) % MOD;
                }
                for (int j = 1; j < l; j++) {
                    for (int k = 0; k <= i - l; k++) {
                        for (int t = 0; t <= k; t++) {
                            d[j][k] = (d[j][k] + d[j - 1][k - t] * c[i - j - k + t][t + 1] % MOD * b[t + 1] % MOD * (t + 1) % MOD) % MOD;
                        }
                    }
                }
                b[i] = (b[i] + d[l - 1][i - l] * INV2) % MOD;
            }

            b[i] = (b[i] + bh[i]) % MOD;

            System.out.println(b[i]);
        }
        out.println(b[n]);

        in.close();
        out.close();
    }

    public void run() {
        try {
            solve();
        } catch (IOException e) {
        }
    }

    public static void main(String[] arg) {
        new Thread(new cacti_as()).start();
    }
}