using System;
using System.Collections.Generic;
using System.Linq;

namespace OEIS
{
    internal class Towers
    {
        private List<long> _ways;

        static void Main(string[] args)
        {
            var t = new Towers();
            for (var i = 0; i <= 50; i++)
            {
                Console.Write(t.Calculate(i) + ", ");
            }
            Console.ReadLine();
        }

        public Towers()
        {
        }

        // first create all partitions
        // an example partition, for n=4, is
        // 1 1 1 1
        // 1 1 2
        // 1 3
        // 2 2
        // 4
        //
        // then each set of towers of the same size gets a configuration
        // for 2 2 2, for instance, there are two possibilities for each
        // tower (a single level with two blocks or two levels with one
        // block each) but the total possibilities is not 2*2*2=8, since
        // the configuration "1/1,2,2" is the same as "2,1/1,2". Instead
        // we want to choose three towers with repetition from two possibilities
        // which is 3+2-1 choose 3, aka 4C3 = 4.
        //
        // multiply all the sets of towers of the same size and sum
        // over partitions for the result
        //
        // for n=4, then,
        //
        // 1 1 2 becomes "1 with multiplicity 2" and "2 with multiplicity 1".
        // There is f(1)=1 way to build a tower of size 1, and
        // f(1)+2-1 choose 2 = 2C2 = 1 way to build 2 towers of size 1.
        //
        // f(2)=2 ways to build a tower of size 2.
        //
        // 1 1 2 has 1*2=2 ways to be built. Sum over each of the 5 partitions of n=4.
        public long Calculate(int n)
        {
            if (n == 0) return 1;

            return Partitions(n).Sum(partition => (from multiple in Multiples(partition)
                                                   let possibilitiesForOneTower = F(multiple[0])
                                                   let numTowers = multiple.Count
                                                   select Choose(possibilitiesForOneTower + numTowers - 1, numTowers)).Aggregate<long, long>(1,
                    (current, ways) => current * ways));
        }

        private long F(int n)
        {
            if (_ways == null)
            {
                _ways = new List<long>() { 1, 1, 2 };
            }
            if (_ways.Count <= n)
            {
                for (var i = _ways.Count; i <= n; i++)
                {
                    _ways.Add(_ways[i - 1] + _ways[i - 2]);
                }
            }
            return _ways[n];
        }

        private static IEnumerable<List<int>> Multiples(List<int> partition)
        {
            var index = 0;
            while (index < partition.Count)
            {
                var startIndex = index;
                var num = partition[startIndex];
                while (index < partition.Count && partition[index] == num)
                {
                    index++;
                }
                yield return partition.GetRange(startIndex, index - startIndex);
            }
        }

        public static IEnumerable<List<int>> Partitions(int n)
        {
            var a = new List<int>();
            if (n == 0) yield break;
            if (n == 1)
            {
                a.Add(1);
                yield return a;
                yield break;
            }
            for (var i = 0; i < n; i++) a.Add(0);
            var k = 1;
            a[1] = n;
            while (k != 0)
            {
                var x = a[k - 1] + 1;
                var y = a[k] - 1;
                k -= 1;
                while (x <= y)
                {
                    a[k] = x;
                    y -= x;
                    k += 1;
                }
                a[k] = x + y;
                yield return a.GetRange(0, k + 1);
            }
        }
        public static long Choose(long n, long m)
        {
            if (n < m) return 0;
            long r = 1;
            for (long i = 0; i < m; i++)
            {
                r *= n - i;
                r /= i + 1;
            }
            return r;
        }
    }
}