The Knight's Scouting Mission

This happened while Cube Kingdom and Prism Kingdom were at war. The two countries together can be seen as one chessboard with $r$ rows and $c$ columns. The capital of Cube Kingdom sits at $(1, 1)$ and the capital of Prism Kingdom sits at $(r, c)$.

Cube Kingdom once sent a knight to scout Prism Kingdom. A knight moves two squares horizontally or vertically and then one more square in the perpendicular direction, which makes it a quick scout. The story says the knight never left the board, travelled the shortest distance, and had worked out that distance and the number of shortest routes in advance, so the mission succeeded without being caught.

Now that the two countries have made peace, the king of Cube Kingdom told this story to the king of Prism Kingdom, and both kings became curious about the distance and the count. You are a great scientist, so solve this problem for them.

The first line contains the number of rows $r$ and the number of columns $c$, separated by a space. ($1 \le r, c \le 400$)

On the first line, print the shortest distance the knight travelled and the number of shortest routes, separated by a space. The count can be very large, so print it modulo $1000000009$.

If the two capitals are the same square, the distance is $0$ and the count is $1$.

If no route from $(1, 1)$ to $(r, c)$ exists at all, the knight lied to the king, so print only None.