시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 41 1 1 100.000%

문제

김주성은 사실 뛰어난 발레 실력을 숨기고 있다. 그는 매일 밤 열심히 발레 연습을 한다.

그는 항상 연습하는 곳의 바닥을 m행 n열의 정사각형 칸들로 나누어 놓고 춤을 춘다. 그가 춤을 추는 방식은 이 직사각형 격자판 위를 점프하여 돌아다니는 것인데, 현재 위치하고 있는 칸에서 점프할 수 있는 위치는 체스판 위의 나이트 (knight)가 이동할 수 있는 곳과 같다. (나이트의 이동 규칙을 모르는 경우 검색해 볼 것. ㅜ.ㅜ) 김주성은 특정한 위치에서 춤을 시작하여, 특정한 위치에서 춤을 마치고 싶다.

밤중에 쿵쿵거리면 실례이므로, 바닥에 방석을 깔아 놓고 춤을 추려고 한다. 방석은 격자칸 한 칸에 꼭 맞는 크기이고, 몇 개의 칸에는 방석이 이미 놓여 있다. 특히, 김 조교가 현재 서 있는 위치와, 최종적으로 도달하려고 하는 위치에는 이미 방석이 놓여 있다.

여러분이 할 일은 최소한의 방석을 더 놓아서 김주성의 춤이 가능하도록 만들고, 그렇게 할 수 있는 방법이 모두 몇 가지인지 계산하는 것이다. 다만, 돌멩이가 놓여 있는 칸도 있는데, 그 부분에는 방석을 놓지 않는다. 부상의 위험이 있기 때문이다.

입력

첫째 줄에 m과 n이 주어진다. (1≤m, n≤30)
  이어지는 m개의 줄에는 각 행의 정보를 제공하는 n개의 숫자가 주어진다. 0은 맨땅, 1은 방석이 깔린 곳 중 김주성이 춤을 시작하거나 마치지 않는 위치, 2는 돌멩이가 있는 위치, 3은 김주성이 춤을 시작하는 위치 (방석이 깔려 있음), 4는 김주성이 춤을 마치는 위치 (방석이 깔려 있음)이다.

출력

첫 줄에 필요한 최소의 방석 수를 출력한다. 만약 아무리 방석을 많이 놓아도 김주성의 춤이 불가능할 경우엔, -1을 출력한다. 둘째 줄엔 방석을 놓는 방법의 수를 출력한다. (이 수는 64-bit signed integer 범위 내에 있음을 보장한다.) 만약 첫 줄에 -1을 출력한 경우에는, 둘째 줄은 출력하지 않는다.

예제 입력

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0

예제 출력

2
3

힌트

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0
입출력 예시의 세 가지 경우는 다음과 같다. X표 친 곳에 방석을 놓으면 된다.

1 0 0 0 0     1 0 X 0 0     1 0 X 0 0
3 0 X 0 0     3 0 0 0 0     3 0 0 0 X
0 0 2 0 0     0 X 2 0 0     0 0 2 0 0
0 X 0 4 0     0 0 0 4 0     0 0 0 4 0