using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Dictionary<string,long> map=new Dictionary<string,long>();

        //The problem is to count all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down

        //Time complexity of non optimized version becomes O(2^n/2) as for evrry level of recursion, we are doubling our number of operations. Same for Fibonacci sequence

        Console.WriteLine(GridTraveller_1(2,3,map));

    }

    public static long GridTraveller(int m,int n,Dictionary<string,long> map)

    {

        string key=String.Concat(m.ToString(),',',n.ToString());

        if(map!=null) {if(map.ContainsKey(key)) return map[key];}

        if(m==0 || n==0)    return 0;

        if (m==n && m==1)   return 1;

        map[key]=GridTraveller(m-1,n,map)+GridTraveller(m,n-1,map);

        return map[key];

    }

    public static long GridTraveller_1(int m,int n,Dictionary<string,long> map)

    {

        //Possible traversals are RU,RD and R

        string key=String.Concat(m.ToString(),',',n.ToString());

        if(map!=null) {if(map.ContainsKey(key)) return map[key];}

        if(m==0 || n==0)    return 0;

        if (m==n && m==1)   return 1;

        //Traversing Right means decreasing the grid columns by 1..so m,n-1

        //Traversing Right Up means decreasing the grid columns by 1 and grid rows by 1...so m-1,n-1

        map[key]=GridTraveller_1(m+1,n-1,map)+GridTraveller_1(m,n-1,map)+GridTraveller_1(m-1,n-1,map);

        return map[key];

    }

}