나이트의 염탐

큐브 왕국과 프리즘 왕국이 한창 전쟁 중이던 시절의 이야기다. 두 나라를 합쳐 $r$행 $c$열짜리 체스판 하나로 볼 수 있고, 큐브 왕국의 수도는 $(1, 1)$에, 프리즘 왕국의 수도는 $(r, c)$에 있다.

큐브 왕국은 프리즘 왕국을 염탐하려고 나이트를 보냈다. 나이트는 가로나 세로로 두 칸 이동한 뒤 그 방향과 수직으로 한 칸 더 이동하는 날쌘 염탐꾼이다. 나이트는 체스판 밖으로 나가지 않으면서 최단 거리로 이동했고, 그 거리와 최단 경로의 가짓수를 미리 조사해 둔 덕분에 들키지 않고 염탐에 성공했다고 전해진다.

두 나라가 화해한 지금, 큐브 왕국의 국왕이 프리즘 왕국의 국왕에게 이 이야기를 들려주자 두 국왕 모두 그 거리와 가짓수가 얼마였는지 궁금해졌다. 위대한 과학자인 당신이 이 문제를 풀어 달라.

첫 줄에 행의 수 $r$과 열의 수 $c$가 공백을 사이에 두고 주어진다. ($1 \le r, c \le 400$)

첫 줄에 나이트가 이동한 최단 거리와 최단 경로의 가짓수를 공백을 사이에 두고 출력한다. 가짓수가 매우 클 수 있으므로 $1000000009$로 나눈 나머지를 출력한다.

두 수도가 같은 칸이면 거리는 $0$이고 가짓수는 $1$이다.

$(1, 1)$에서 $(r, c)$로 가는 경로가 아예 없으면 나이트가 국왕을 속인 것이므로 None만 출력한다.