Palindrome Paths

An N x N array contains digits from 0 to 9. A path starts from any cell and then moves to one of the 8 neighboring cells, including diagonal neighbors, on each step. A complete path visits exactly L cells, including the starting cell.

If the digits written on the visited cells, read in visiting order, form a palindrome, the path is called a palindrome path.

The same cell may be visited more than once. However, a move may not stay in the same cell, so each step must move to a different adjacent cell. Moving back to a previously visited cell is allowed.

Given the array, count the number of palindrome paths.

A palindrome is a sequence that reads the same from the front and from the back. The sequences {1}, {1 1}, and {1 3 1} are palindromes.

The first line contains N and L. (1 <= N <= 20, 1 <= L <= 20)

Each of the next N lines contains one row of the array: N integers between 0 and 9, separated by spaces.

Print the number of palindrome paths. This value is at most 2^31 - 1.