시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
60 초 256 MB 13 10 8 88.889%

문제

강호는 M행 N열 크기의 체스판 위에 나이트를 놓으려고 한다. 각각의 칸에는 최대 1개의 나이트가 놓여질 수 있다.

이 때, 체스판 위에 있는 나이트가 서로 공격을 할 수 있으면 안된다. 나이트가 놓여져 있을 때, 공격할 수 있는 칸의 위치는 아래 그림에 X로 표시되어 있다.

체스판의 크기가 주어졌을 때, 나이트를 놓을 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (T ≤ 10)가 주어진다. 각각의 테스트 케이스는 두 정수 M과 N으로 이루어져 있다. (1 ≤ M ≤ 4, 1 ≤ N ≤ 109)

출력

각각의 테스트 케이스마다, 나이트를 놓을 수 있는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

4
1 2
2 2
3 2
4 31415926

예제 출력 1

4
16
36
413011760

힌트

W3sicHJvYmxlbV9pZCI6IjEwNTYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMDk4XHVjNzc0XHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwva25pZ2h0cy5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTlweDsgd2lkdGg6MjI5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzE1XHVkNjM4XHViMjk0IE1cdWQ1ODkgTlx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjY2I0XHVjMmE0XHVkMzEwIFx1YzcwNFx1YzVkMCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHViMTkzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgMVx1YWMxY1x1Yzc1OCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHViMTkzXHVjNWVjXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMsIFx1Y2NiNFx1YzJhNFx1ZDMxMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWMxMWNcdWI4NWMgXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDAgWFx1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTA1NjJcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTUwcHg7IHdpZHRoOjE0NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMDk4XHVjNzc0XHVkMmI4XHViOTdjIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKFQgJmxlOyAxMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IE1cdWFjZmMgTlx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IE0gJmxlOyA0LCAxICZsZTsgTiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHViMDk4XHVjNzc0XHVkMmI4XHViOTdjIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwOVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDU2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktuaWdodHMiLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2tuaWdodHMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE5cHg7IHdpZHRoOjIyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1hZ251cyBpcyB0aGUgeW91bmdlc3QgY2hlc3MgZ3JhbmRtYXN0ZXIgZXZlci4gSGUgbG92ZXMgY2hlc3Mgc28gbXVjaCB0aGF0IGhlIGhhcyBkZWNpZGVkIHRvIGRlY29yYXRlIGhpcyBob21lIHdpdGggY2hlc3MgcGllY2VzLiBUbyBkZWNvcmF0ZSBoaXMgbG9uZyBjb3JyaWRvciwgaGUgaGFzIGRlY2lkZWQgdG8gdXNlIGtuaWdodHMuIEhpcyBjb3JyaWRvciBpcyBjb3ZlcmVkIGJ5IGJlYXV0aWZ1bCBtYXJibGUgc3F1YXJlcyBvZiBNIHJvd3MgYW5kIE4gY29sdW1ucy4gSGUgd2FudHMgdG8gcHV0IHRoZSBrbmlnaHRzIHBpZWNlcyBpbnRvIHNvbWUgKG9yIHBvc3NpYmx5IG5vbmUpIG9mIHRoZXNlIGNlbGxzLiBFYWNoIGNlbGwgd2lsbCBjb250YWluIGF0IG1vc3Qgb25lIGtuaWdodC48XC9wPlxyXG5cclxuPHA+VGhlIHNwZWNpYWwgdGhpbmcgaW4gaGlzIGFycmFuZ2VtZW50IGlzIG5vIHBhaXIgb2Yga25pZ2h0cyBjYW4gYXR0YWNrIGVhY2ggb3RoZXIuIChUd28ga25pZ2h0cyBjYW4gYXR0YWNrIGVhY2ggb3RoZXIgaWYgdGhleSBhcmUgcGxhY2VkIGluIG9wcG9zaXRlIGNvcm5lciBjZWxscyBvZiBhIDIgYnkgMyByZWN0YW5nbGUpLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgZGltZW5zaW9uIG9mIHRoZSBsb25nIGNvcnJpZG9yLCB5b3VyIHRhc2sgaXMgdG8gY2FsY3VsYXRlIGhvdyBtYW55IHdheXMgTWFnbnVzIGNhbiBhcnJhbmdlIGhpcyBrbmlnaHQgcGllY2VzLiBUd28gYXJyYW5nZW1lbnRzIGFyZSBjb25zaWRlcmVkIGRpZmZlcmVudCBpZiB0aGVyZSBleGlzdHMgYSBjZWxsIHdoaWNoIGNvbnRhaW5zIGEga25pZ2h0IGluIHRoZSBmaXJzdCBhcnJhbmdlbWVudCBidXQgbm90IGluIHRoZSBvdGhlciBhcnJhbmdlbWVudC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCAoVCAmbGU7IDEwKS4gVGhlbiBUIHRlc3QgY2FzZXMgZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiAyIG51bWJlcnM6IE0sIHRoZSBudW1iZXIgb2Ygcm93cywgYW5kIE4sIHRoZSBudW1iZXIgb2YgY29sdW1ucy4gKDEgJmxlOyBNICZsZTsgNCwgMSAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIG51bWJlciBvZiBwb3NzaWJsZSB3YXlzIG1vZHVsbyAxLDAwMCwwMDAsMDA5ICgxMDxzdXA+OTxcL3N1cD4gKyA5KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==