시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhYzE1XHVkNjM4XHViMjk0IE1cdWQ1ODkgTlx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjY2I0XHVjMmE0XHVkMzEwIFx1YzcwNFx1YzVkMCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHViMTkzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgMVx1YWMxY1x1Yzc1OCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHViMTkzXHVjNWVjXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YywgXHVjY2I0XHVjMmE0XHVkMzEwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjZjVcdWFjYTlcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMCBYXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMDU2MlwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTBweDsgd2lkdGg6MTQ1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjY2I0XHVjMmE0XHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoVCAmbGU7IDEwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggTVx1YWNmYyBOXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgxICZsZTsgTSAmbGU7IDQsIDEgJmxlOyBOICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWIwOThcdWM3NzRcdWQyYjhcdWI5N2MgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA5XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNTYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS25pZ2h0cyIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwva25pZ2h0cy5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTlweDsgd2lkdGg6MjI5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TWFnbnVzIGlzIHRoZSB5b3VuZ2VzdCBjaGVzcyBncmFuZG1hc3RlciBldmVyLiBIZSBsb3ZlcyBjaGVzcyBzbyBtdWNoIHRoYXQgaGUgaGFzIGRlY2lkZWQgdG8gZGVjb3JhdGUgaGlzIGhvbWUgd2l0aCBjaGVzcyBwaWVjZXMuIFRvIGRlY29yYXRlIGhpcyBsb25nIGNvcnJpZG9yLCBoZSBoYXMgZGVjaWRlZCB0byB1c2Uga25pZ2h0cy4gSGlzIGNvcnJpZG9yIGlzIGNvdmVyZWQgYnkgYmVhdXRpZnVsIG1hcmJsZSBzcXVhcmVzIG9mIE0gcm93cyBhbmQgTiBjb2x1bW5zLiBIZSB3YW50cyB0byBwdXQgdGhlIGtuaWdodHMgcGllY2VzIGludG8gc29tZSAob3IgcG9zc2libHkgbm9uZSkgb2YgdGhlc2UgY2VsbHMuIEVhY2ggY2VsbCB3aWxsIGNvbnRhaW4gYXQgbW9zdCBvbmUga25pZ2h0LjxcL3A+XHJcblxyXG48cD5UaGUgc3BlY2lhbCB0aGluZyBpbiBoaXMgYXJyYW5nZW1lbnQgaXMgbm8gcGFpciBvZiBrbmlnaHRzIGNhbiBhdHRhY2sgZWFjaCBvdGhlci4gKFR3byBrbmlnaHRzIGNhbiBhdHRhY2sgZWFjaCBvdGhlciBpZiB0aGV5IGFyZSBwbGFjZWQgaW4gb3Bwb3NpdGUgY29ybmVyIGNlbGxzIG9mIGEgMiBieSAzIHJlY3RhbmdsZSkuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBkaW1lbnNpb24gb2YgdGhlIGxvbmcgY29ycmlkb3IsIHlvdXIgdGFzayBpcyB0byBjYWxjdWxhdGUgaG93IG1hbnkgd2F5cyBNYWdudXMgY2FuIGFycmFuZ2UgaGlzIGtuaWdodCBwaWVjZXMuIFR3byBhcnJhbmdlbWVudHMgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50IGlmIHRoZXJlIGV4aXN0cyBhIGNlbGwgd2hpY2ggY29udGFpbnMgYSBrbmlnaHQgaW4gdGhlIGZpcnN0IGFycmFuZ2VtZW50IGJ1dCBub3QgaW4gdGhlIG90aGVyIGFycmFuZ2VtZW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGlzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIChUICZsZTsgMTApLiBUaGVuIFQgdGVzdCBjYXNlcyBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIDIgbnVtYmVyczogTSwgdGhlIG51bWJlciBvZiByb3dzLCBhbmQgTiwgdGhlIG51bWJlciBvZiBjb2x1bW5zLiAoMSAmbGU7IE0gJmxlOyA0LCAxICZsZTsgTiAmbGU7IDEwPHN1cD45PFwvc3VwPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgbW9kdWxvIDEsMDAwLDAwMCwwMDkgKDEwPHN1cD45PFwvc3VwPiArIDkpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d