| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 90 | 30 | 22 | 30.137% |
2048이라는 게임이 있다. 이 게임은 4ドル\times 4$ 격자판 위에 1ドル \times 1$ 크기의 조각이 있고, 방향키를 눌러 같은 수가 적혀 있는 조각을 모두 그 방향으로 이동해 합칠 수 있는 게임이다. 한 번 이동할 때마다 임의의 위치에 2ドル^{1}$부터 2ドル^{16}$까지의 2ドル$의 거듭제곱인 수가 적힌 타일이 생성되며, 격자판이 가득 차 있고, 조각을 합치지 못하는 상황이 오면 게임이 종료된다.
유능한 해커이지만 2048에는 그렇게 유능하지 않은 협이는 이 게임에서 2ドル^{17}$ 타일을 만들고 싶어졌다. 격자판이 2ドル^{17}$을 담기에 너무 좁다고 생각했던 협이는 자신의 해킹 실력을 발휘해 가로 크기를 $w,ドル 세로 크기를 $h$로 바꾸어 게임을 했다. 그럼에도 불구하고 협이는 2ドル^{17}$ 타일을 만드는 데에 번번이 실패했다.
협이는 2ドル^{16}$ 타일 두 개를 한 번 합치는 것도 못하냐는 도훈이의 핀잔에, 게임이 끝나는 경우의 수가 너무 많기에 어쩔 수 없다는 주장을 펼치려 했다. 그러나 격자판의 가로 크기 $w$가 너무 커져 버린 나머지, 협이는 경우의 수를 계산하는 것을 어려워하고 있다. 협이를 대신해서 게임이 종료되었을 때 격자판의 최종 상태로 가능한 경우의 수를 구해주자. 최종 상태란 인접한 칸에 같은 숫자가 적혀 있지 않으면서, 모든 칸에 16ドル$가지 중 하나의 타일이 존재하는 상태를 말한다.
첫째 줄에 질의의 개수 $Q$가 주어진다. $(1 \leq Q \leq 1,000円)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 줄마다 격자판의 크기 $h_i$ 와 $w_i$가 공백으로 구분되어 주어진다. $(1 \leq h_i \leq 6; 1 \leq w_i \leq 10^{18})$
각 질의에 대해, 최종 상태로 가능한 경우의 수를 1ドル,000円,000円,007円$으로 나눈 나머지를 한 줄에 하나씩 순서대로 출력하라.
3 1 3 2 2 4 4
3600 50640 579307730
첫 번째 질의에서, 세 칸이 일렬로 늘어서 있는 경우 첫 번째 칸을 선택하는 경우의 수는 16ドル$가지, 첫 번째 칸이 선택되었을 때 두 번째 칸을 선택하는 경우의 수는 15ドル$가지, 첫 번째와 두 번째 칸이 선택되었을 때 세 번째 칸을 선택하는 경우의 수는 15ドル$가지이므로 경우의 수는 16ドル \times 15 \times 15 = 3,600円$이다.
두 번째 질의는 다음과 같이 네 가지 경우로 나누어 계산할 수 있다.
구하고자 하는 경우의 수는 16ドル \times 15 + 16 \times 15 \times 14 + 16 \times 15 \times 14 + 16 \times 15 \times 14 \times 13 = 50,640円$이다.
세 번째 질의의 경우의 수는 3ドル,929円,961円,678円,089円,039円,280円$이므로, 이를 1ドル,000円,000円,007円$로 나눈 나머지인 579ドル,307円,730円$을 출력한다.