题目描述

为了便于牛们欣赏和锻炼，农夫$\red{JOHN}$在他的农场上新添加了一个美丽的池塘。

$\red{JOHN}$的池塘是一个长方形，他已经把它划分成了$\red{M}$行$\red{N}$列的小正方行 $\red{(1 <= M <= 30}$; $\red{1 <= N <= 30). }$某些正方行里是石头，另外一 些则是特别结实的荷叶，其余则只有清水。

为了锻炼，$\red{Bessie}$想从一片荷叶跳到另外一片。她的每一次跳跃都是一个象棋中的马步：两行一列或一行两列。 $\red{JOHN}$看到了$\red{Bessie}$并且发现有时$\red{Bessie}$没有办法达到她的目标荷叶。

他准备添加一些荷叶来让$\red{Bessie}$完成她的目标。当然，荷叶不能放在石头上。 帮助$\red{JOHN}$找出他最少要放多少片荷叶和他一共有多少种放最少片荷叶的方案。

输入格式

第$\red{1}$行： 两个整数， $\red{M }$和 $\red{N}$。

第$\red{2 \sim}$$\red{M+1}$行： 第$\red{i+1}$包含$\red{N}$个数，分别为第$\red{i}$行的$\red{N}$个格子的情况。 $\red{0}$表示格子为空，$\red{1}$表示有一片荷叶，$\red{2}$表示格子里有石头，$\red{3}$表示此格子是$\red{Bessie}$的起点，$\red{4 }$表示此格子是$\red{Bessie}$的目标。

输出格式

第$\red{1}$行： 一个数，最少情况下需要添加的荷叶数目。

如果没有方案存在，输出$\red{- 1}$。

第$\red{2}$行： 一个数，达到最小值的方案总数。

这个数保证不超过内设$\red{64}$位整数$\red{(long long/ int64)}$的大小。如果第一行是$\red{-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

提示

输入解释：

池塘含$\red{4}$行$\red{5}$列。$\red{Bessie}$在第$\red{2}$行第$\red{1}$列并且想跳到第$\red{4}$行第$\red{4}$列。池塘里有$\red{1}$块 石头和$\red{3}$片荷叶

输出解释：

至少需要$\red{2}$片荷叶。一共有三种摆法： 第$\red{4}$行第$\red{2}$列，第$\red{2}$行第$\red{3}$列 第$\red{1}$行第$\red{3}$列，第$\red{3}$行第$\red{2}$列 第$\red{1}$行第$\red{3}$列，第$\red{2}$行第$\red{5}$列

R1C2,R2C3     R1C3,R3C2     R1C3,R2C5
          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