시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 56 20 20 42.553%

문제

Cube World와 Baekjoon World가 한창 전쟁 중일 때 있었던 일입니다. 이 두 나라는 r행 c열의 체스판으로 생각할 수 있고, Cube World의 수도는 (1,1)에, Baekjoon World의 수도는 (r,c)에 있습니다.

Cube World에서 Baekjoon World를 염탐하기 위해서 나이트를 보낸 적이 있습니다. 나이트는 가로 또는 세로로 두 칸 이동한 뒤, 수직한 방향으로 한 칸 이동할 수 있는 날렵한 염탐꾼입니다. 나이트는 최단거리로 이동했고, 그 거리와 가짓수를 미리 조사하여 들키지 않고 성공적으로 염탐하고 왔다고 전해집니다.

두 나라가 화해한 지금, Cube World의 국왕이 Baekjoon World의 국왕에게 이 이야기를 들려주자, 둘 모두 그 거리와 가짓수가 얼마였는지 궁금해졌습니다. 위대한 과학자인 당신이 이 문제를 해결해 주세요!

입력

첫 줄에 행의 수 r과 열의 수 c가 공백을 사이에 두고 주어집니다. (1 ≤ r, c ≤ 400)

출력

첫 줄에 나이트가 이동한 거리와 그 가짓수를 공백을 사이에 두고 출력합니다. 가짓수가 너무 클 수 있으므로, 1 000 000 009로 나눈 나머지를 출력합니다.

만약 나이트가 국왕을 속였다면, 나이트의 목숨은 없기 때문에 None만 출력합니다.

예제 입력 1

4 4

예제 출력 1

2 2

예제 입력 2

4 5

예제 출력 2

3 1

예제 입력 3

2 4

예제 출력 3

None

힌트

W3sicHJvYmxlbV9pZCI6IjExMDg0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1YzVmY1x1ZDBkMCIsImRlc2NyaXB0aW9uIjoiPHA+Q3ViZSBXb3JsZFx1YzY0MCBCYWVram9vbiBXb3JsZFx1YWMwMCBcdWQ1NWNcdWNjM2QgXHVjODA0XHVjN2MxIFx1YzkxMVx1Yzc3YyBcdWI1NGMgXHVjNzg4XHVjNWM4XHViMzU4IFx1Yzc3Y1x1Yzc4NVx1YjJjOFx1YjJlNC4gXHVjNzc0IFx1YjQ1MCBcdWIwOThcdWI3N2NcdWIyOTQgclx1ZDU4OSBjXHVjNWY0XHVjNzU4IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgQ3ViZSBXb3JsZFx1Yzc1OCBcdWMyMThcdWIzYzRcdWIyOTQgKDEsMSlcdWM1ZDAsIEJhZWtqb29uIFdvcmxkXHVjNzU4IFx1YzIxOFx1YjNjNFx1YjI5NCAocixjKVx1YzVkMCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkN1YmUgV29ybGRcdWM1ZDBcdWMxMWMgQmFla2pvb24gV29ybGRcdWI5N2MgXHVjNWZjXHVkMGQwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHViY2Y0XHViMGI4IFx1YzgwMVx1Yzc3NCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YjI5NCBcdWFjMDBcdWI4NWMgXHViNjEwXHViMjk0IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWI0NTAgXHVjZTc4IFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWI0YTQsIFx1YzIxOFx1YzljMVx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIwYTBcdWI4MzVcdWQ1NWMgXHVjNWZjXHVkMGQwXHVhZmJjXHVjNzg1XHViMmM4XHViMmU0LiBcdWIwOThcdWM3NzRcdWQyYjhcdWIyOTQgXHVjZDVjXHViMmU4XHVhYzcwXHViOWFjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU4OFx1YWNlMCwgXHVhZGY4IFx1YWM3MFx1YjlhY1x1YzY0MCBcdWFjMDBcdWM5ZDNcdWMyMThcdWI5N2MgXHViYmY4XHViOWFjIFx1Yzg3MFx1YzBhY1x1ZDU1OFx1YzVlYyBcdWI0ZTRcdWQwYTRcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM1ZmNcdWQwZDBcdWQ1NThcdWFjZTAgXHVjNjU0XHViMmU0XHVhY2UwIFx1YzgwNFx1ZDU3NFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YjA5OFx1Yjc3Y1x1YWMwMCBcdWQ2NTRcdWQ1NzRcdWQ1NWMgXHVjOWMwXHVhZTA4LCBDdWJlIFdvcmxkXHVjNzU4IFx1YWQ2ZFx1YzY1NVx1Yzc3NCBCYWVram9vbiBXb3JsZFx1Yzc1OCBcdWFkNmRcdWM2NTVcdWM1ZDBcdWFjOGMgXHVjNzc0IFx1Yzc3NFx1YzU3Y1x1YWUzMFx1Yjk3YyBcdWI0ZTRcdWI4MjRcdWM4ZmNcdWM3OTAsIFx1YjQ1OCBcdWJhYThcdWI0NTAgXHVhZGY4IFx1YWM3MFx1YjlhY1x1YzY0MCBcdWFjMDBcdWM5ZDNcdWMyMThcdWFjMDAgXHVjNWJjXHViOWM4XHVjNjAwXHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YzJiNVx1YjJjOFx1YjJlNC4gXHVjNzA0XHViMzAwXHVkNTVjIFx1YWNmY1x1ZDU1OVx1Yzc5MFx1Yzc3OCBcdWIyZjlcdWMyZTBcdWM3NzQgXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NzQgXHVjOGZjXHVjMTM4XHVjNjk0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQ1ODlcdWM3NTggXHVjMjE4IHJcdWFjZmMgXHVjNWY0XHVjNzU4IFx1YzIxOCBjXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKDEgJmxlOyByLCBjICZsZTsgNDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWFjNzBcdWI5YWNcdWM2NDAgXHVhZGY4IFx1YWMwMFx1YzlkM1x1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWMwMFx1YzlkM1x1YzIxOFx1YWMwMCBcdWIxMDhcdWJiMzQgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsIDEgMDAwIDAwMCAwMDlcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVhZDZkXHVjNjU1XHVjNzQ0IFx1YzE4ZFx1YzYwMFx1YjJlNFx1YmE3NCwgXHViMDk4XHVjNzc0XHVkMmI4XHVjNzU4IFx1YmFhOVx1YzIyOFx1Yzc0MCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIE5vbmVcdWI5Y2MgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMDg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS25pZ2h0XHUyMDE5cyBTaG9ydGVzdCBQYXRoIiwiZGVzY3JpcHRpb24iOiI8cD5NYXN0ZXIgTGkgbGlrZXMgdG8gcGxheSB2YXJpb3VzIHR5cGVzIG9mIGNoZXNzIGFuZCB3YXMgdGhpbmtpbmcgYWJvdXQgaG93IGVmZmljaWVudCB0aGUga25pZ2h0IHBpZWNlIG1vdmVzIGJldHdlZW4gcG9zaXRpb25zIG9uIGEgY2hlc3MgYm9hcmQuIEl0IGlzIGtub3duIHRoYXQgdGhlIGtuaWdodCB0cmF2ZWxzIChpbiBvbmUgbW92ZSkgdHdvIGNlbGxzIGluIG9uZSBkaXJlY3Rpb24gdGhlbiBvbmUgY2VsbCBpbiB0aGUgb3RoZXIgYXhpcyBhcyBzaG93biBpbiB0aGUgaW50ZXJuYXRpb25hbCA4ICZ0aW1lczsgOCBjaGVzc2JvYXJkIHNob3duIGluIEZpZ3VyZSAxLiBUaGVyZSBhcmUgYWxzbyB2YXJpb3VzIGZsYXZvdXJzIG9mIGNoZXNzLCBpbmNsdWRpbmcgdGhlIENoaW5lc2UgdmVyc2lvbiAoeGlhbmdxaSkgc2hvd24gaW4gRmlndXJlIDIsIHdoZXJlIHRoZSBrbmlnaHQgaXMgcGxhY2VkIG9uIHRoZSBpbnRlcnNlY3Rpb25zIG9mIGxpbmVzIChlcXVpdmFsZW50IHRvIGEgMTAgJnRpbWVzOyA5IGNlbGwtYmFzZWQgYm9hcmQpLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZVwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzExMDg1XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMxOHB4OyB3aWR0aDozMDdweFwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTEwODVcLzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzEzcHg7IHdpZHRoOjI5NnB4XCIgXC8+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPkZpZ3VyZSAxOiBJbnRlcm5hdGlvbmFsIEJvYXJkPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMjogWGlhbmdxaSBCb2FyZDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+V2l0aCB2YXJpb3VzIHNpemVzIG9mIGJvYXJkcywgTWFzdGVyIExpIHdhbnRzIHRvIGtub3cgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGtuaWdodCBtb3ZlcyB0byB0cmF2ZWwgZnJvbSBvcHBvc2l0ZSBjb3JuZXJzIG9mIGEgYm9hcmQgKGUuZy4gZ28gZnJvbSBjZWxsIDFhIHRvIGNlbGwgOGgpLiBJbiBhZGRpdGlvbiwgaGUgd2FudHMgdG8ga25vdyB0aGUgdG90YWwgbnVtYmVyIG9mIGRpZmZlcmVudCBtaW5pbXVtIHBhdGhzLiBDYW4geW91IGhlbHAgaGltIGNhbGN1bGF0ZSB0aGlzIGluZm9ybWF0aW9uPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIHRlc3QgY2FzZS48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMsIHIgYW5kIGMgKDEgJmxlOyByLCBjICZsZTsgNDAwKSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBjZWxscyBpbiB2ZXJ0aWNhbCBkaXJlY3Rpb24gKHJvd3MpIGFuZCBob3Jpem9udGFsIGRpcmVjdGlvbiAoY29sdW1ucykgZm9yIHRoZSBjaGVzc2JvYXJkLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlcmUgaXMgbm8gcGF0aCBmb3IgdGhlIGtuaWdodCB0byB0YWtlLCBvdXRwdXQgTm9uZS4gT3RoZXJ3aXNlLCBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBzaG93aW5nIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Yga25pZ2h0IG1vdmVzIGFuZCBhIGNvdW50IG9mIHRoZSBudW1iZXIgb2YgZGlzdGluY3QgcGF0aHMgb2YgdGhhdCBzaG9ydGVzdCBkaXN0YW5jZSBiZXR3ZWVuIHR3byBvcHBvc2l0ZSBjb3JuZXJzLiBTaW5jZSB0aGUgbnVtYmVyIG9mIHBhdGhzIGNhbiBiZSBxdWl0ZSBsYXJnZSwgb3V0cHV0IHRoaXMgbnVtYmVyIG1vZHVsbyAxIDAwMCAwMDAgMDA5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==