시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)69574384.314%

문제

하지만 KCPC 운영을 위해서는 세진이는 운영진 현황을 안 세진 채로 둘 순 없다.

KCPC 2025의 운영진은 KAIST 소속의 동우, 컴퓨터학과(Computer Science) 소속 동현이, 물리학과(Physics) 세진이, 사이버국방학과(Cyber Defense) 지훈(가명)이 등 다양한 소속의 사람들로 구성되어 있다.

세진이는 KCPC 운영진의 자리를 배치하려고 한다. 대회 운영진들이 있을 방에는 $N\times M$개의 자리가 $N$행 $M$열의 모양으로 배치되어 있으며, 세진이는 각 자리에 K, C, P 중 하나를 배치할 것이다. 이때 임의의 연속된 두 행과 연속된 두 열로 이루어진 $2\times 2$ 자리에 대해, K, C, P가 각각 $1$개, $2$개, $1$개로 구성되어 있어야 한다.

$N$과 $M$이 주어졌을 때 세진이가 조건에 맞게 배치할 수 있는 경우의 수를 구해보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\leq T\leq 100\, 000)$가 주어진다.

두 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 정수 $N,M(2\leq N,M\leq 100\, 000)$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 정답을 $998\, 244\, 353$로 나눈 나머지를 출력한다.

예제 입력 1

2
2 2
3 4

예제 출력 1

12
50

$N=2$, $M=2$의 경우 아래와 같이 $12$가지의 가능한 배치가 있다.

$N=3$, $M=4$의 경우 아래와 같이 $50$가지의 가능한 배치가 있다.

예제 입력 2

5
22 55
14 44
29 33
54 72
64 50

예제 출력 2

640851440
260044614
285458402
114348170
670665702

예제 입력 3

10
99919 12635
46569 92101
87047 85638
34674 91051
53804 65650
55973 84926
90893 44625
83971 98077
13120 95724
74687 81487

예제 출력 3

935738495
229565321
888256074
105871422
327288010
712182018
606333518
264331652
185098346
881744380

노트

이 문제의 제목은 kidw0124와 foxpython의 $N$시간의 고민과 회의 끝에 결정되었다. 문제의 $N$과는 무관하다.

W3sicHJvYmxlbV9pZCI6IjM1MTYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTM4XHVjOWM0XHVjNTQ0LCBcdWQ1YTVcdWFlMzBcdWFjMDAgXHVjMTM4XHVjOWM0IFx1YWY0M1x1YmMyZFx1YzVkMFx1YzExYywgXHVjOWMwXHViMjk0IFx1YWY0M1x1Yzc4ZVx1Yzc0NCBcdWMxMzhcdWM5YzQgXHVjNTRhXHVjNzNjXHViODI0IFx1ZDU3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTU4XHVjOWMwXHViOWNjIEtDUEMgXHVjNmI0XHVjNjAxXHVjNzQ0IFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWMxMzhcdWM5YzRcdWM3NzRcdWIyOTQgXHVjNmI0XHVjNjAxXHVjOWM0IFx1ZDYwNFx1ZDY2OVx1Yzc0NCBcdWM1NDggXHVjMTM4XHVjOWM0IFx1Y2M0NFx1Yjg1YyBcdWI0NTggXHVjMjFjIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+S0NQQyAyMDI1XHVjNzU4IFx1YzZiNFx1YzYwMVx1YzljNFx1Yzc0MCBLQUlTVCBcdWMxOGNcdWMxOGRcdWM3NTggXHViM2Q5XHVjNmIwLCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWQ1NTlcdWFjZmMoQ29tcHV0ZXIgU2NpZW5jZSkgXHVjMThjXHVjMThkIFx1YjNkOVx1ZDYwNFx1Yzc3NCwgXHViYjNjXHViOWFjXHVkNTU5XHVhY2ZjKFBoeXNpY3MpIFx1YzEzOFx1YzljNFx1Yzc3NCwgXHVjMGFjXHVjNzc0XHViYzg0XHVhZDZkXHViYzI5XHVkNTU5XHVhY2ZjKEN5YmVyIERlZmVuc2UpIFx1YzljMFx1ZDZjOChcdWFjMDBcdWJhODUpXHVjNzc0IFx1YjRmMSBcdWIyZTRcdWM1OTFcdWQ1NWMgXHVjMThjXHVjMThkXHVjNzU4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzhcdWM5YzRcdWM3NzRcdWIyOTQgS0NQQyBcdWM2YjRcdWM2MDFcdWM5YzRcdWM3NTggXHVjNzkwXHViOWFjXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjMwMFx1ZDY4YyBcdWM2YjRcdWM2MDFcdWM5YzRcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YmMyOVx1YzVkMFx1YjI5NCAkTlxcdGltZXMgTSRcdWFjMWNcdWM3NTggXHVjNzkwXHViOWFjXHVhYzAwICROJFx1ZDU4OSAkTSRcdWM1ZjRcdWM3NTggXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzEzOFx1YzljNFx1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjNWQwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5LPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkM8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UDxcL2NvZGU+PFwvc3Bhbj4gXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWI0NTAgXHVkNTg5XHVhY2ZjIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWI0NTAgXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCAkMlxcdGltZXMgMiQgXHVjNzkwXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU3NCwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPks8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+QzxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5QPFwvY29kZT48XC9zcGFuPlx1YWMwMCBcdWFjMDFcdWFjMDEgJDEkXHVhYzFjLCAkMiRcdWFjMWMsICQxJFx1YWMxY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+JE4kXHVhY2ZjICRNJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YzEzOFx1YzljNFx1Yzc3NFx1YWMwMCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHVhYzhjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggJFQoMVxcbGVxIFRcXGxlcSAxMDBcXCwgMDAwKSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkVCRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmNjNFx1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNTI5IFx1YzgxNVx1YzIxOCAkTixNKDJcXGxlcSBOLE1cXGxlcSAxMDBcXCwgMDAwKSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgJFQkXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjYzRcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzUyOSBcdWM4MTVcdWIyZjVcdWM3NDQgJDk5OFxcLCAyNDRcXCwgMzUzJFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4MWNcdWJhYTlcdWM3NDAgPGEgaHJlZj1cIlwva2lkdzAxMjRcIj5raWR3MDEyNDxcL2E+XHVjNjQwIDxhIGhyZWY9XCJcL3VzZXJcL2ZveHB5dGhvblwiPmZveHB5dGhvbjxcL2E+XHVjNzU4ICROJFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWFjZTBcdWJiZmNcdWFjZmMgXHVkNjhjXHVjNzU4IFx1YjA1ZFx1YzVkMCBcdWFjYjBcdWM4MTVcdWI0MThcdWM1YzhcdWIyZTQuIFx1YmIzOFx1YzgxY1x1Yzc1OCAkTiRcdWFjZmNcdWIyOTQgXHViYjM0XHVhZDAwXHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPiROPTIkLCAkTT0yJFx1Yzc1OCBcdWFjYmRcdWM2YjAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCAkMTIkXHVhYzAwXHVjOWMwXHVjNzU4IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMzBcdWNlNThcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2EyN2ZhNTk3LWM4YWUtNDE3NC1iYzgwLWQxY2Y3YjY0NTE0ZFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjAwcHg7IG1heC13aWR0aDogMTAwJTtcIiBcLz48XC9wPlxyXG5cclxuPHA+JE49MyQsICRNPTQkXHVjNzU4IFx1YWNiZFx1YzZiMCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0ICQ1MCRcdWFjMDBcdWM5YzBcdWM3NTggXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYmE5NjkxNjItNjA0Mi00YzhkLWIyYWUtNzhiYjZiNTk1MGMxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2MDBweDsgbWF4LXdpZHRoOiAxMDAlO1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjM1MTYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VqaW4sIHdoZXJlIHRoZSBkYXJrbmVzcyBzZXRzIGluLCB3YXRjaCB0aGUgc2lsZW5jZSBzYWlsIGluIiwiZGVzY3JpcHRpb24iOiI8cD5CdXQgZm9yIHRoZSBLQ1BDIHRvIHJ1biBzbW9vdGhseSwgU2VqaW4gY2Fubm90IGp1c3Qgc3RheSBpbi48XC9wPlxyXG5cclxuPHA+VGhlIEtDUEMgMjAyNSBzdGFmZiBpcyBjb21wcmlzZWQgb2YgcGVvcGxlIGZyb20gdmFyaW91cyBhZmZpbGlhdGlvbnMsIGluY2x1ZGluZyBEb25nd29vIGZyb20gS0FJU1QsIERvbmdoeXVuIGZyb20gQ29tcHV0ZXIgU2NpZW5jZSwgU2VqaW4gZnJvbSBQaHlzaWNzLCBhbmQgSmlodW4gKHBzZXVkb255bSkgZnJvbSBDeWJlciBEZWZlbnNlLjxcL3A+XHJcblxyXG48cD5TZWppbiB3YW50cyB0byBhcnJhbmdlIHRoZSBzZWF0cyBmb3IgdGhlIG1haW4gc3RhZmYgb2YgS0NQQy4gSW4gdGhlIHN0YWZmIHJvb20sIHRoZXJlIGFyZSAkTlxcdGltZXMgTSQgc2VhdHMgYXJyYW5nZWQgYXMgYSBncmlkIHdpdGggJE4kIHJvd3MgYW5kICRNJCBjb2x1bW5zLCBhbmQgU2VqaW4gd2lsbCBhc3NpZ24gZWFjaCBzZWF0IG9uZSBvZiA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+SzxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5DPFwvY29kZT48XC9zcGFuPiwgb3IgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlA8XC9jb2RlPjxcL3NwYW4+LiBGb3IgZXZlcnkgJDJcXHRpbWVzIDIkIGJsb2NrIGZvcm1lZCBieSB0d28gY29uc2VjdXRpdmUgcm93cyBhbmQgdHdvIGNvbnNlY3V0aXZlIGNvbHVtbnMsIHRoZSBmb3VyIHNlYXRzIG11c3QgY29uc2lzdCBvZiBleGFjdGx5ICQxJCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+SzxcL2NvZGU+PFwvc3Bhbj4sICQyJCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+QzxcL2NvZGU+PFwvc3Bhbj5zLCBhbmQgJDEkIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5QPFwvY29kZT48XC9zcGFuPi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gJE4kIGFuZCAkTSQsIGNvbXB1dGUgdGhlIG51bWJlciBvZiB3YXlzIFNlamluIGNhbiBtYWtlIGFuIGFycmFuZ2VtZW50IHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgJFQoMVxcbGVxIFRcXGxlcSAxMDBcXCwgMDAwKSQgaXMgZ2l2ZW4uPFwvcD5cclxuXHJcbjxwPkZyb20gdGhlIHNlY29uZCBsaW5lIG92ZXIgdGhlIG5leHQgJFQkIGxpbmVzLCBmb3IgZWFjaCB0ZXN0IGNhc2UsIGludGVnZXJzICROLE0oMlxcbGVxIE4sTVxcbGVxIDEwMFxcLCAwMDApJCBhcmUgZ2l2ZW4gc2VwYXJhdGVkIGJ5IHNwYWNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gcm9tIHRoZSBmaXJzdCBsaW5lIG92ZXIgdGhlIG5leHQgJFQkIGxpbmVzIGZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBhbnN3ZXIgbW9kdWxvICQ5OThcXCwgMjQ0XFwsIDM1MyQuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSB0aXRsZSBvZiB0aGlzIHByb2JsZW0gd2FzIGNob3NlbiBhZnRlciAkTiQgaG91cnMgb2YgZGViYXRlIGJldHdlZW4gPGEgaHJlZj1cIlwvdXNlclwva2lkdzAxMjRcIj5raWR3MDEyNDxcL2E+IGFuZCA8YSBocmVmPVwiXC91c2VyXC9mb3hweXRob25cIj5mb3hweXRob248XC9hPi4gVGhlICROJCBoZXJlIGlzIHVucmVsYXRlZCB0byB0aGUgb25lIGluIHRoZSBwcm9ibGVtLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5Gb3IgJE49MiQgYW5kICRNPTIkLCB0aGVyZSBhcmUgJDEyJCB2YWxpZCBhcnJhbmdlbWVudHMgYXMgc2hvd24gYmVsb3cuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTI3ZmE1OTctYzhhZS00MTc0LWJjODAtZDFjZjdiNjQ1MTRkXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2MDBweDsgbWF4LXdpZHRoOiAxMDAlO1wiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgJE49MyQgYW5kICRNPTQkLCB0aGVyZSBhcmUgJDUwJCB2YWxpZCBhcnJhbmdlbWVudHMgYXMgc2hvd24gYmVsb3cuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYmE5NjkxNjItNjA0Mi00YzhkLWIyYWUtNzhiYjZiNTk1MGMxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2MDBweDsgbWF4LXdpZHRoOiAxMDAlO1wiIFwvPjxcL3A+XHJcbiJ9XQ==