발레리노

김주성은 밤마다 발레를 연습한다. 연습장 바닥은 m행 n열의 정사각형 격자이며, 그는 체스의 나이트처럼 이동한다.

각 칸에는 맨땅, 이미 놓인 방석, 돌멩이, 시작 위치, 도착 위치 중 하나의 상태가 있다. 시작 위치와 도착 위치에는 이미 방석이 있으며, 돌멩이가 있는 칸에는 방석을 놓을 수 없다.

이미 방석이 있는 칸과 새로 방석을 놓은 칸만 밟을 수 있을 때, 시작 위치에서 도착 위치까지 이동할 수 있도록 추가해야 하는 방석 수의 최솟값과, 그 최솟값을 달성하는 방석 배치 방법의 수를 구하라. 방석 배치 방법은 새로 방석을 놓는 칸들의 집합으로 구분한다.

첫째 줄에 두 정수 m과 n이 주어진다. 1 <= m, n <= 30이다.

다음 m개의 줄에는 각 행의 상태를 나타내는 n개의 정수가 주어진다.

• 0: 맨땅
• 1: 이미 방석이 놓인 칸
• 2: 돌멩이가 있는 칸
• 3: 시작 위치이며, 이미 방석이 놓인 칸
• 4: 도착 위치이며, 이미 방석이 놓인 칸

첫째 줄에 추가로 놓아야 하는 방석 수의 최솟값을 출력한다.

도착 위치까지 이동할 수 없으면 -1을 출력하고 종료한다.

이동할 수 있다면 둘째 줄에 그 최솟값을 달성하는 방석 배치 방법의 수를 출력한다. 이 값은 64-bit signed integer 범위 안에 있음이 보장된다.

보이는 테스트에서는 방석 두 개를 추가해야 하며, 가능한 최소 배치가 세 가지 있다.