테트리스

파나마 운하를 건설하는 데에는 2천만 시간에 달하는 인간의 노동이 필요했습니다. 반면 2003년 한 해에만 전 세계 사람들이 컴퓨터 카드 게임(솔리테어)에 90억 시간을 썼습니다. 안타깝게도 인류가 테트리스에 얼마나 많은 시간을 쏟았는지는 알 수 없지만, 이 분야에서의 경험에 비추어 보면 그 시간 역시 매우 길 것이라고 짐작합니다.

너비가 4칸, 높이가 $n$칸인 직사각형 판이 있습니다. 판의 첫 번째 행에 있는 각 칸의 상태가 주어집니다. 서로 다른 7가지 종류의 조각(그림 참고)을 각 종류마다 원하는 만큼 사용할 수 있습니다. 이 조각들은 테트리스 게임에서 흔히 쓰이는 조각들입니다. 다만 "긴" 조각은 4칸이 아니라 3칸을 차지한다는 점에 유의하세요. 조각은 회전할 수 있습니다.

조각들로 판 전체를 빈틈없이 덮으려고 합니다. 조각끼리 서로 겹치거나 판 밖으로 벗어날 수 없고, 이미 덮여 있는 칸을 다시 덮을 수도 없습니다. 판 전체를 덮는 서로 다른 방법은 모두 몇 가지일까요?

첫째 줄에 테스트의 개수를 나타내는 자연수 $d$ ($1 \le d \le 100$)가 주어집니다.

각 테스트는 두 줄로 이루어집니다. 첫째 줄에는 판의 높이를 나타내는 정수 $n$ ($1 \le n \le 10^9$)이 주어집니다. 둘째 줄에는 첫 번째 행의 상태를 나타내는 4개의 문자가 주어지며, 각 문자는 * 또는 . 입니다. *는 이미 덮여 있는 칸을, .는 비어 있는 칸을 뜻합니다.

각 테스트에 대해, 주어진 조각들로 판 전체를 덮는 서로 다른 방법의 수를 구하고, 그 값을 $10^6$으로 나눈 나머지를 한 줄에 하나씩 출력하세요.