문제
Game of RUN은 Game of Go(바둑)와 비슷하지만 2차원의 정사각형 격자 대신에 1차원 격자를 사용하는 2인용 게임이다.
Game of RUN의 규칙은 다음과 같다.
- 두 플레이어가 번갈아서 흑돌 또는 백돌을 격자 위에 원하는 만큼 놓는다. 0ドル$개를 놓는 것도 허용된다.
- 한 가지 색깔의 돌이 1칸 이상의 연속한 구간을 차지할 때 그 구간 전체를 그룹이라고 하자. 흑돌 3개가 연달아 놓여 있다면 그 중 흑돌 2개나 1개만을 포함하는 구간은 그룹이 아니다. 이때, 모든 그룹은 적어도 하나의 빈 칸과 이웃하고 있어야 한다. 예를 들어, 아래와 같은 경우들은 각각 흑돌의 그룹과 백돌의 그룹이 빈 칸과 이웃하고 있지 않으므로 올바른 게임 상태가 아니다.
길이 $n$인 게임판에서 가능한 모든 서로 다른 게임 상태의 수를 1ドル 000 000 007$로 나눈 나머지를 구하시오.
출력
각 테스트 케이스에 대해 문제의 정답을 한 줄에 출력한다.
제한
- 1ドル\le T\le 10 000$
- 1ドル\le n\le 1 000 000$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 10 | $T \le 3, n \le 3$
|
| 2 | 15 | $T \le 10, n \le 10$
|
| 3 | 20 | $T \le 17, n \le 17$
|
| 4 | 25 | $T \le 1000, n \le 1000$
|
| 5 | 30 | 추가적인 제약 조건이 없다.
|
W3sicHJvYmxlbV9pZCI6IjMzODAxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiR2FtZSBvZiBSVU4iLCJkZXNjcmlwdGlvbiI6IjxwPkdhbWUgb2YgUlVOXHVjNzQwIEdhbWUgb2YgR28oXHViYzE0XHViNDUxKVx1YzY0MCBcdWJlNDRcdWMyYjdcdWQ1NThcdWM5YzBcdWI5Y2MgMlx1Y2MyOFx1YzZkMFx1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhY2E5XHVjNzkwIFx1YjMwMFx1YzJlMFx1YzVkMCAxXHVjYzI4XHVjNmQwIFx1YWNhOVx1Yzc5MFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgMlx1Yzc3OFx1YzZhOSBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkdhbWUgb2YgUlVOXHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViYzg4XHVhYzA4XHVjNTQ0XHVjMTFjIFx1ZDc1MVx1YjNjYyBcdWI2MTBcdWIyOTQgXHViYzMxXHViM2NjXHVjNzQ0IFx1YWNhOVx1Yzc5MCBcdWM3MDRcdWM1ZDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWIxOTNcdWIyOTRcdWIyZTQuICQwJFx1YWMxY1x1Yjk3YyBcdWIxOTNcdWIyOTQgXHVhYzgzXHViM2M0IFx1ZDVjOFx1YzZhOVx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkNTVjIFx1YWMwMFx1YzljMCBcdWMwYzlcdWFlNTRcdWM3NTggXHViM2NjXHVjNzc0IDFcdWNlNzggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzVmMFx1YzE4ZFx1ZDU1YyBcdWFkNmNcdWFjMDRcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTYwIFx1YjU0YyBcdWFkZjggXHVhZDZjXHVhYzA0IFx1YzgwNFx1Y2NiNFx1Yjk3YyBcdWFkZjhcdWI4ZjlcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWQ3NTFcdWIzY2MgM1x1YWMxY1x1YWMwMCBcdWM1ZjBcdWIyZWNcdWM1NDQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWFkZjggXHVjOTExIFx1ZDc1MVx1YjNjYyAyXHVhYzFjXHViMDk4IDFcdWFjMWNcdWI5Y2NcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc0MCBcdWFkZjhcdWI4ZjlcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWFkZjhcdWI4ZjlcdWM3NDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJlNDggXHVjZTc4XHVhY2ZjIFx1Yzc3NFx1YzZjM1x1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjRlNFx1Yzc0MCBcdWFjMDFcdWFjMDEgXHVkNzUxXHViM2NjXHVjNzU4IFx1YWRmOFx1YjhmOVx1YWNmYyBcdWJjMzFcdWIzY2NcdWM3NTggXHVhZGY4XHViOGY5XHVjNzc0IFx1YmU0OCBcdWNlNzhcdWFjZmMgXHVjNzc0XHVjNmMzXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YWM4Y1x1Yzc4NCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvODk2MDRjNTctOWZkNS00NTMyLWJiZjgtMTU0MjVjNTA1NzIxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImhlaWdodDogMTAwcHg7IHdpZHRoOiA4MDBweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0ICRuJFx1Yzc3OCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWM4Y1x1Yzc4NCBcdWMwYzFcdWQwZGNcdWM3NTggXHVjMjE4XHViOTdjICQxIDAwMCAwMDAgMDA3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4ICRUJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjJlNFx1Yzc0YyAkVCRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YzgxNVx1YzIxOCAkbiRcdWM3NTggXHVhYzEyXHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViYjM4XHVjODFjXHVjNzU4IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlIFRcXGxlIDEwIDAwMCQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIG5cXGxlIDEgMDAwIDAwMCQ8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JFQgXFxsZSAzLCBuIFxcbGUgMyQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRUIFxcbGUgMTAsIG4gXFxsZSAxMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiRUIFxcbGUgMTcsIG4gXFxsZSAxNyQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPiRUIFxcbGUgMTAwMCwgbiBcXGxlIDEwMDAkPFwvcD5cclxuIiwic3VidGFzazUiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzM4MDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHYW1lIG9mIFJVTiIsImRlc2NyaXB0aW9uIjoiPHA+R2FtZSBvZiBSVU4mbmJzcDtpcyBhIHR3by1wbGF5ZXIgZ2FtZSBzaW1pbGFyIHRvIHRoZSBHYW1lIG9mIEdvLiBJbnN0ZWFkIG9mIGEgdHdvLWRpbWVuc2lvbmFsIGdyaWQgaW4gR2FtZSBvZiBHbywgR2FtZSBvZiBSVU4gdXNlcyBhIG9uZS1kaW1lbnNpb25hbCBncmlkLjxcL3A+XHJcblxyXG48cD5UaGUgcnVsZXMgb2YgR2FtZSBvZiBSVU4gYXJlIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIHR3byBwbGF5ZXJzIHRha2UgdHVybnMsIHBsYWNpbmcgemVybyBvciBtb3JlIGJsYWNrIG9yIHdoaXRlIHN0b25lcyBvbiB0aGUgZ3JpZC48XC9saT5cclxuXHQ8bGk+V2hlbiBvbmUgb3IgbW9yZSBzdG9uZXMgb2YgYSBzaW5nbGUgY29sb3IgYXJlIHBsYWNlZCBvbiBjb25zZWN1dGl2ZSBjZWxscywgdGhlIGVudGlyZXR5IG9mIHN1Y2ggYSByZWdpb24gaXMgY2FsbGVkIGEgZ3JvdXAuIElmIHRocmVlIGJsYWNrIHN0b25lcyBhcmUgcGxhY2VkIGluIGEgcm93LCB0aGUgcmVnaW9ucyBjb250YWluaW5nIG9ubHkgb25lIG9yIHR3byBvZiB0aG9zZSBzdG9uZXMgYXJlIG5vdCBhIGdyb3VwLiBFdmVyeSBncm91cCBtdXN0IGJlIGFkamFjZW50IHRvIGFuIGVtcHR5IGNlbGwuIEZvciBleGFtcGxlLCB0aGUgZm9sbG93aW5nIGNhc2VzIGFyZSBub3QgdmFsaWQgZ2FtZSBzdGF0ZXMgc2luY2UgYSBncm91cCBvZiBibGFjayBcLyZuYnNwO3doaXRlIHN0b25lcyByZXNwZWN0aXZlbHkgdmlvbGF0ZSB0aGlzIHJ1bGUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84OTYwNGM1Ny05ZmQ1LTQ1MzItYmJmOC0xNTQyNWM1MDU3MjFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiAxMDBweDsgd2lkdGg6IDgwMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5DYWxjdWxhdGUgdGhlIG51bWJlciBvZiBhbGwgZGlzdGluY3QgdmFsaWQgc3RhdGVzIG9uIGEgZ3JpZCBvZiBsZW5ndGggJG4kLCBtb2R1bG8gJDFcXDsgMDAwXFw7IDAwMFxcOyAwMDckLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICRUJC48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgJFQkIGxpbmVzIGVhY2ggY29udGFpbiBhIHBvc2l0aXZlIGludGVnZXIgJG4kLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGFuc3dlciBvbiBhIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMVxcbGUgVFxcbGUgMTBcXDsgMDAwJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgblxcbGUgMVxcOyAwMDBcXDsgMDAwJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kVCBcXGxlIDMsIG4gXFxsZSAzJC48XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRUIFxcbGUgMTAsIG4gXFxsZSAxMCQuPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kVCBcXGxlIDE3LCBuIFxcbGUgMTckLjxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+JFQgXFxsZSAxXFw7MDAwLCBuIFxcbGUgMVxcOzAwMCQuPFwvcD5cclxuIiwic3VidGFzazUiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiJ9XQ==