题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

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

这个数保证不超过内设${64}$位整数${(long long/ int64)}$的大小。如果第一行是${-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}$列。${Bessie}$在第${2}$行第${1}$列并且想跳到第${4}$行第${4}$列。池塘里有${1}$块 石头和${3}$片荷叶

输出解释：

至少需要${2}$片荷叶。一共有三种摆法： 第${4}$行第${2}$列，第${2}$行第${3}$列 第${1}$行第${3}$列，第${3}$行第${2}$列 第${1}$行第${3}$列，第${2}$行第${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