시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 469 173 120 35.503%

문제

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

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

배열이 주어졌을 때, 팰린드롬 경로의 개수를 구하는 프로그램을 작성하시오. 만들 수 있는 팰린드롬의 개수를 세는 것이 아니고, 경로의 개수를 세는 것임에 유의한다.

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

입력

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

출력

첫째 줄에 팰린드롬 경로의 개수를 출력한다. 이 값은 int 범위를 넘지 않는다.

예제 입력

3 3
3 1 4
1 5 9
2 6 5

예제 출력

48

힌트