// Arup Guha
// 4/6/2024
// Introductory DP Code for Junior Knights

import java.util.*;

public class dp {
	
	public static long[] fibs;
	public static long[][] pascal;
	
	public static void main(String[] args) {

		// Set up memo array for memo solution to combinations.
		int n = 36;
		int k = 20;
		pascal = new long[n+1][k+1];
		for (int i=0; i<=n; i++)
			Arrays.fill(pascal[i], -1L);
	
		// Set up any of the functions to time.
		long sT = System.currentTimeMillis();
		long ans = comboDP(36, 20);
		long eT = System.currentTimeMillis();
		System.out.println(ans+" took "+(eT-sT)+" ms.");
	}
	
	// Recursive version of Fibonacci -> this is slow due to redundant recursive calls.
	public static long fib(int n) {
		
		// fib(0) = 0, fib(1) = 1
		if (n < 2) return n;
		
		// Fibonacci formula.
		return fib(n-1)+fib(n-2);
	}
	
	// Wrapper function to run recursive memoized fibonacci function.
	public static long fibWrapper(int n) {
		fibs = new long[n+1];
		Arrays.fill(fibs, -1);
		return fibMemo(n);
	}
	
	// Returns Fib(n) via memoization.
	public static long fibMemo(int n) {
		
		// fib(0) = 0, fib(1) = 1
		if (n < 2) return n;
		
		// Hey, I did this before just return the answer!
		if (fibs[n] != -1) return fibs[n];
		
		// Fibonacci formula - first store before returning.
		return fibs[n] = fibMemo(n-1)+fibMemo(n-2);
	}
	
	// Fibonacci DP solution doesn't use recursion.
	public static long fibDP(int n) {
		
		// Build storage.
		long[] res = new long[n+1];
		
		// Store base cases.
		res[0] = 0;
		res[1] = 1;
		
		// Compute all cases bottom up.
		for (int i=2; i<=n; i++)
			res[i] = res[i-1]+res[i-2];
		
		// return result.
		return res[n];
	}
	
	// Recursively returns "n choose k".
	public static long combo(int n, int k) {
		
		// Base cases.
		if (k == 0 || k == n) return 1;
		if (k > n) return 0;
		
		// This is the recursive definition for combinations.
		return combo(n-1,k-1) + combo(n-1,k);
	}
	
	// Memoized version of combinations.
	public static long comboMemo(int n, int k) {
		
		// Base cases.
		if (k == 0 || k == n) return 1;
		if (k > n) return 0;
		
		// We've done this before, just return the answer.
		if (pascal[n][k] != -1) return pascal[n][k];
		
		// Recurse, store answer then return.
		return pascal[n][k] = comboMemo(n-1,k-1) + comboMemo(n-1,k);
	}
	
	// Assume k >= 0 && k <= n.
	public static long comboDP(int n, int k) {
		
		// Store all necessary subanswers here.
		long[][] res = new long[n+1][k+1];
		
		for (int i=0; i<=n; i++) {
			
			// First item is always 1.
			res[i][0] = 1;
			
			// Last item is one.
			if (i<=k) res[i][i] = 1;
			
			// Pascal Triangle Formula
			for (int j=1; j<=k && j<i; j++)
				res[i][j] = res[i-1][j-1]+res[i-1][j];	
		}
		
		// Return answer.
		return res[n][k];
	}
}