Ballerino

Jusung Kim practices ballet every night. The practice floor is divided into an m by n grid of square cells, and each move he makes is the same as a knight move in chess.

Each cell is one of the following: bare floor, an already cushioned cell, a stone, the starting position, or the ending position. The starting and ending positions already have cushions, and a cushion cannot be placed on a cell containing a stone.

He may step only on cells that already have cushions or cells where you add new cushions. Compute the minimum number of additional cushions needed so that he can move from the starting position to the ending position, and the number of cushion placements that achieve that minimum. Two placements are different if the set of newly cushioned cells differs.

The first line contains two integers m and n, where 1 <= m, n <= 30.

Each of the next m lines contains n integers describing one row of the grid.

• 0: bare floor
• 1: a cell that already has a cushion
• 2: a cell containing a stone
• 3: the starting position, which already has a cushion
• 4: the ending position, which already has a cushion

Print the minimum number of additional cushions on the first line.

If it is impossible to reach the ending position, print -1 and stop.

Otherwise, print the number of placements that achieve the minimum on the second line. This value is guaranteed to fit in a 64-bit signed integer.

In the visible test, two additional cushions are required, and there are three minimum placements.