using System;
using System.Numerics;

namespace Oeis3122
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 500;
            // K=3: A003122
            // K=4: A003123
            // K=5: A005979
            const int K = 3;

            // Binomial coefficients
            var binom = new BigInteger[N + K][];
            for (int n = 0; n < binom.Length; n++)
            {
                binom[n] = new BigInteger[n + 1];
                binom[n][0] = 1;
                for (int k = 1; k < n; k++) binom[n][k] = binom[n - 1][k - 1] + binom[n - 1][k];
                binom[n][n] = 1;
            }

            // Catalan numbers
            var catalan = new BigInteger[N + 1];
            catalan[0] = 1;
            for (int n = 1; n < catalan.Length; n++) catalan[n] = catalan[n - 1] * (4 * n - 2) / (n + 1);

            // Rathie (1973) gives the recurrence
            //   f(n, K) = p(n, K) - sum_{s=0}^{n-1} A(s+K, n-s) f(s, K)
            // where p is a hypergeometric term and
            //   A(n, s) = sum_{m=1}^s binomial(n, m) B(s, m)
            //   B(s, m) = sum multinomial(m; a_1,...,a_k) prod_i catalan(i)^{2a_i}
            // where the sum in B is over partitions of s into exactly m parts having frequency representation
            // 1^{a_1} 2^{a_2} ...
            // In order to get a polynomial time recurrence we consider C(s, q, m) which is the same sum but
            // over partitions of s into exactly m parts each of which is at most q. Then we can factor out the
            // parts which are exactly q to get a recurrence:
            //   C(s, q, m) = sum_{a_q} binomial(m, a_q) catalan(q)^{2a_q} C(s - a_q q, q - 1, m - a_q)
            // and obviously B(s, m) = C(s, s, m)
            var C = new BigInteger[N + 1][,];
            var a = new BigInteger[N + 1];
            BigInteger p = 0;
            for (int n = 0; n <= N; n++)
            {
                C[n] = new BigInteger[n + 1, n + 1];
                if (n == 0) C[n][0, 0] = 1;

                for (int q = 1; q <= n; q++)
                {
                    for (int m = 1; m <= n; m++)
                    {
                        BigInteger sum = 0, r = 0, mr = catalan[q] * catalan[q];
                        for (int f = 0, mf = m, nf = n; f <= m && mf <= nf; f++, mf--, nf -= q)
                        {
                            r = f == 0 ? 1 : r * mr;

                            // Optimisation: C(s, q, m) = C(s, s, m) when q > s
                            var qf = Math.Min(nf, q - 1);
                            if (mf * qf >= nf) sum += binom[m][f] * r * C[nf][qf, mf];
                        }
                        C[n][q, m] = sum;
                    }
                }

                p = n == 0 ? catalan[K - 2]
                           : p * (2 * (2*n + 2*K - 5) * (2*n + K - 1) * (2*n + K - 2)) / ((n + K - 1) * (n + K) * n);
                var an = p;
                for (int k = 1; k <= n; k++)
                {
                    BigInteger An = 0;
                    for (int m = 1; m <= k && m <= n - k + 3; m++) An += binom[n - k + 3][m] * C[k][k, m];
                    an -= An * a[n - k];
                }
                a[n] = an;
                Console.WriteLine("{0} {1}", n, an);
            }
        }
    }
}