/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	  public static void main(String[] args)
  {
    int arr[][] =
    {
      { 1, 2, 3 },
      { 4, 6, 5 },
      { 3, 2, 1 }
    };
    int dp[][][] = new int[3][3][20];
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < 3; j++)
        for (int k = 0; k < 20; k++)
          dp[i][j][k] = -1;
    System.out.println(countPath(arr, 0, 0, 0, 12, dp));
  }

  public static int countPath(int arr[][], int i, int j, int coinSum, int k, int dp[][][])
  {

    if (i == arr.length - 1 && j == arr.length - 1 && (coinSum + arr[i][j]) == 12)
      return 1;
    if (i >= arr.length || j >= arr.length)
      return 0;
    if (dp[i][j][coinSum] != -1)
    {
      System.out.println("cache hittttt..... !!!!!!");
      return dp[i][j][coinSum];
    }
    dp[i][j][coinSum] =
      countPath(arr, i + 1, j, coinSum + arr[i][j], k, dp) + countPath(arr, i, j + 1, coinSum + arr[i][j], k, dp);
    return dp[i][j][coinSum];
  }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCSAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykKICB7CiAgICBpbnQgYXJyW11bXSA9CiAgICB7CiAgICAgIHsgMSwgMiwgMyB9LAogICAgICB7IDQsIDYsIDUgfSwKICAgICAgeyAzLCAyLCAxIH0KICAgIH07CiAgICBpbnQgZHBbXVtdW10gPSBuZXcgaW50WzNdWzNdWzIwXTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMzsgaSsrKQogICAgICBmb3IgKGludCBqID0gMDsgaiA8IDM7IGorKykKICAgICAgICBmb3IgKGludCBrID0gMDsgayA8IDIwOyBrKyspCiAgICAgICAgICBkcFtpXVtqXVtrXSA9IC0xOwogICAgU3lzdGVtLm91dC5wcmludGxuKGNvdW50UGF0aChhcnIsIDAsIDAsIDAsIDEyLCBkcCkpOwogIH0KCiAgcHVibGljIHN0YXRpYyBpbnQgY291bnRQYXRoKGludCBhcnJbXVtdLCBpbnQgaSwgaW50IGosIGludCBjb2luU3VtLCBpbnQgaywgaW50IGRwW11bXVtdKQogIHsKCiAgICBpZiAoaSA9PSBhcnIubGVuZ3RoIC0gMSAmJiBqID09IGFyci5sZW5ndGggLSAxICYmIChjb2luU3VtICsgYXJyW2ldW2pdKSA9PSAxMikKICAgICAgcmV0dXJuIDE7CiAgICBpZiAoaSA+PSBhcnIubGVuZ3RoIHx8IGogPj0gYXJyLmxlbmd0aCkKICAgICAgcmV0dXJuIDA7CiAgICBpZiAoZHBbaV1bal1bY29pblN1bV0gIT0gLTEpCiAgICB7CiAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiY2FjaGUgaGl0dHR0dC4uLi4uICEhISEhISIpOwogICAgICByZXR1cm4gZHBbaV1bal1bY29pblN1bV07CiAgICB9CiAgICBkcFtpXVtqXVtjb2luU3VtXSA9CiAgICAgIGNvdW50UGF0aChhcnIsIGkgKyAxLCBqLCBjb2luU3VtICsgYXJyW2ldW2pdLCBrLCBkcCkgKyBjb3VudFBhdGgoYXJyLCBpLCBqICsgMSwgY29pblN1bSArIGFycltpXVtqXSwgaywgZHApOwogICAgcmV0dXJuIGRwW2ldW2pdW2NvaW5TdW1dOwogIH0KfQ==