시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB141757939138.184%

문제

N×N배열에 0부터 9까지의 숫자들이 적혀 있다. 이 배열의 임의의 한 칸에서 시작하여, 매번 인접(상하좌우 및 대각선)해 있는 8개의 칸들 중 하나로 이동하여 총 L칸(시작하는 칸을 포함하여)을 이동하면 하나의 경로가 완성된다. 이때 지나온 순서대로 각 칸에 적혀 있는 숫자를 나열한 것이 팰린드롬이 될 때, 그 경로를 팰린드롬 경로라 한다.

단, 팰린드롬 경로에서는 똑같은 칸을 여러 번 지날 수도 있다. 하지만 같은 자리에 연속으로 계속 있는 것은 안 되고, 매번 8개의 칸들 중 하나로 반드시 이동해야 하지만, 다시 그 칸으로 돌아와서 그 칸을 지나는 것은 허용한다는 것이다.

배열이 주어졌을 때, 팰린드롬 경로의 개수를 구하는 프로그램을 작성하시오.

팰린드롬이란 앞에서부터 읽으나, 뒤에서부터 읽으나 같은 수열을 말한다. 예를 들어 {1}, {1 1}, {1 3 1} 등은 팰린드롬이다.

입력

첫째 줄에 N(1 ≤ N ≤ 20), L(1 ≤ L ≤ 20)이 주어진다. 다음 N개의 줄에는 N개의 정수로 배열의 숫자들이 주어진다.

출력

첫째 줄에 팰린드롬 경로의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.

예제 입력 1

3 3
3 1 4
1 5 9
2 6 5

예제 출력 1

48