은빛 수련 연못

농부 존은 소들이 감상하고 운동할 수 있도록 아름다운 직사각형 연못을 만들었습니다. 연못은 $M$개의 행과 $N$개의 열로 이루어진 격자로 나뉩니다 ($1 \le M \le 30$; $1 \le N \le 30$). 어떤 칸에는 아주 튼튼한 수련잎이 있고, 어떤 칸에는 바위가 있으며, 나머지는 열린 물입니다.

소 베시는 수련잎에서 수련잎으로 뛰어다니며 발레를 연습합니다. 베시는 지금 어떤 수련잎 위에 서 있고, 다른 수련잎으로 가고 싶어 합니다. 베시의 모든 점프는 정확히 체스 나이트의 이동입니다. 즉, 한 방향으로 한 칸 간 뒤 수직 방향으로 두 칸을 가거나(또는 한 방향으로 두 칸 간 뒤 수직 방향으로 한 칸을 갑니다). 베시는 수련잎 위에만 내려설 수 있고, 열린 물이나 바위에는 내려설 수 없습니다.

중간에 필요한 수련잎이 없어서 베시가 목적지에 도달하지 못하는 경우가 있습니다. 알뜰한 농부 존은 나이트 점프의 연속으로 베시가 출발 수련잎에서 목적지 수련잎까지 갈 수 있도록, 가능한 한 적은 수의 새 수련잎만 추가하려고 합니다. 새 수련잎은 열린 물 칸에만 놓을 수 있고, 바위 위에는 놓을 수 없습니다.

농부 존을 도와 다음을 순서대로 구하세요.

1. 베시가 목적지에 도달할 수 있도록 놓아야 하는 추가 수련잎의 최소 개수;
2. 그 최소 개수의 수련잎을 놓는 모든 방법 중에서, 베시가 필요로 하는 최소 점프 횟수;
3. 그 최소 개수의 추가 수련잎과 그 최소 점프 횟수를 모두 사용하는, 출발점에서 목적지까지의 서로 다른 경로의 수. 베시가 내려서는 칸의 순서가 다르면 서로 다른 경로이며, 이 수는 추가 수련잎을 놓을 수 있는 모든 방법을 이미 포함합니다.

• 1번째 줄: 공백으로 구분된 두 정수 $M$과 $N$.
• $2 \ldots M+1$번째 줄: $i+1$번째 줄은 연못의 $i$번째 행을 $N$개의 공백으로 구분된 정수로 나타내며, 다음 값을 사용합니다.
  • 0 — 열린 물
  • 1 — 이미 놓인 수련잎
  • 2 — 바위
  • 3 — 베시가 출발하는 수련잎
  • 4 — 베시가 도달하려는 수련잎

3과 4는 각각 정확히 하나씩 있습니다.

• 1번째 줄: 정수 하나 — 필요한 추가 수련잎의 최소 개수. 베시가 목적지에 결코 도달할 수 없으면 -1만 출력합니다.
• 2번째 줄: 정수 하나 — 그 최소 개수의 추가 수련잎을 놓았을 때 베시가 해야 하는 최소 점프 횟수. 1번째 줄이 -1이면 이 줄은 출력하지 않습니다.
• 3번째 줄: 정수 하나 — 최소 개수의 추가 수련잎과 최소 점프 횟수를 사용하는, 출발점에서 목적지까지의 경로의 수. 1번째 줄이 -1이면 이 줄은 출력하지 않습니다.

예시 연못에서는 수련잎 두 개를 추가해야 합니다. 가능한 두 가지 배치를 아래에 x로 표시했습니다.

0 0 0 1 0 0 0 0     0 0 0 1 0 0 0 0
0 x 0 0 0 2 0 1     0 0 0 0 0 2 0 1
0 0 0 0 x 4 0 0     0 0 x 0 x 4 0 0
3 0 0 0 0 0 1 0     3 0 0 0 0 0 1 0

이렇게 추가하면 베시는 적어도 $6$번 점프해야 하며, 아래에 A부터 G까지 표시한 것처럼 서로 다른 $6$번-점프 경로가 정확히 두 개 있습니다.

0 0 0 C 0 0 0 0     0 0 0 C 0 0 0 0
0 B 0 0 0 2 0 F     0 0 0 0 0 2 0 F
0 0 0 0 D G 0 0     0 0 B 0 D G 0 0
A 0 0 0 0 0 E 0     A 0 0 0 0 0 E 0