Narayana numbers

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace SO.BrutForce
{
    class State: IEquatable<State>
    {
        public long p, q, k;

        public State() { }

        #region IEquatable<State> Members

        public bool Equals(State other)
        {
            return p == other.p && q == other.q && k == other.k;
        }

        public override int GetHashCode()
        {
            return ((p << 40) + (q << 20) + k).GetHashCode();
        }

        #endregion
    }
    struct Pair : IEquatable<Pair>
    {
        public long n, k;
        #region IEquatable<Pair> Members

        public bool Equals(Pair other)
        {
            return n == other.n && k == other.k;
        }

        public override int GetHashCode()
        {
            return ((k << 32) + n).GetHashCode();
        }
        #endregion
    }
    class Program
    {
        const long MODULO = 1000000009L;
        const int MaxN = 50;
        const int MaxK = 10;
        static Dictionary<State, long> memory = new Dictionary<State, long>();
        static Dictionary<Pair, long> pairs = new Dictionary<Pair, long>();

        static TimeSpan timer1 = new TimeSpan();
        static TimeSpan timer2 = new TimeSpan();

        static void Main(string[] args)
        {
            for (int k = 1; k <= MaxK; k++)
            {
                for (int n = k; n <= MaxN; n++)
                {
                    //CheckWithBruteForce(writer, n, k);
                    Solve(n, k);
                }
            }
            Console.WriteLine("{0}", timer1);

            using (var writer = new StreamWriter("../../../output"))
            {
                writer.WriteLine(
                    string.Join(" ", Enumerable.Range(0, MaxN + 2).Select(x => Format(x)))
                );

                Console.WriteLine();
                for (int n = 1; n <= MaxN; n++)
                {
                    writer.Write("{0}: ", Format(n).Substring(1));
                    for (int k = 1; k <= Math.Min(n, MaxK); k++)
                    {
                        writer.Write("{0} ", Format(GetFunc(new Pair { n = n - k, k = k })));
                    }
                    writer.WriteLine();
                }
            }
        }

        private static string Format(long x)
        {
            return string.Format("{0, 10}", x);
        }

        private static void Solve(int n, int k)
        {
            var p = new Pair { n = n, k = k };
            var res1 = GetFunc(p);
        }

        private static void CheckWithBruteForce(StreamWriter writer, int n, int k)
        {
            var state = new State { p = n, q = n, k = k };
            var res1 = Func(state);
            var res2 = F(n - k, k);
            writer.WriteLine("{0,4}.{1,3}.{2}: {3,8} {4,6}", n, k, res1 == res2 ? "OK" : "!!", res1, res2);
        }

        private static long F(long n, long k)
        {
            if (n == 0 || k == 1)
                return 1;

            long sum = 0;
            var p = new Pair { n = n - 1, k = k };
            sum += GetFunc(p) % MODULO;

            for (long j = 1; j < k; j++)
            {
                for (long i = (j == 1) ? 0 : 1; i <= n; i++)
                {
                    p.n = (j == 1) ? i : i - 1; p.k = j;
                    long x = GetFunc(p);

                    p.n = n - i; p.k = k - j;
                    long y = GetFunc(p);

                    sum += x * y;
                    if (sum >= MODULO)
                        sum %= MODULO;
                }
            }
            return sum;
        }

        private static long GetFunc(Pair p)
        {
            long x = 0;

            if (p.n == 0 || p.k == 1)
                x = 1;
            if (pairs.ContainsKey(p))
                x = pairs[p];
            else
            {
                x = F(p.n, p.k);
                pairs[p] = x;
            }
            return x;
        }

        private static long Func(State state)
        {
            if (!(state.p > 0 && state.q > 0 && state.p <= state.q))
                return 0;
            if (state.k == 1)
                return 1;

            if (memory.ContainsKey(state))
                return memory[state];

            long sum = 0;
            for (var i = 1; i <= state.p; i++)
            {;
                for (var j = 1; j <= state.q; j++)
                {
                    var newState = new State { p = state.p - i, q = state.q - j, k = state.k - 1 };
                    long res = 0;

                    if (memory.ContainsKey(newState))
                        res = memory[newState];
                    else
                    {
                        res = Func(newState);
                        memory[newState] = res;
                    }
                    sum += res;
                }
                if (sum >= MODULO)
                    sum = sum % MODULO;
            }
            return sum;
        }
    }
}