오래된 금

아주, 아주 오래전($7$년 전), 당신은 금덩이가 적어도 하나 있다고 알려진 동남아시아의 서동 방향 도로에 제한적이지만 신뢰할 수 있는 금 탐지기를 가지고 있었다. 그 금으로 엄청난 부자가 된 뒤, 당신은 상상할 수 있는 모든 활동을 해 보고 싫증이 났다. 거대한 저택을 돌아다니던 중 그 금을 찾을 때 작성한 메모 몇 장을 발견했다.

메모는 도로의 도표 형태로 되어 있다. 도로의 각 킬로미터마다 다음 $5$개 표시 중 하나가 있다.

• <: 가장 가까운 금덩이가 서쪽에 있음을 나타낸다.

• =: 동쪽과 서쪽에서 가장 가까운 금덩이들이 같은 거리에 있고, 해당 위치에는 금덩이가 없음을 나타낸다.

• >: 가장 가까운 금덩이가 동쪽에 있음을 나타낸다.

• o: 해당 위치에 금덩이가 있음을 나타낸다.

• .: 해당 위치에 관해 알려진 것이 없음을 나타낸다.

$k$개의 미지(.) 위치에는 각각 독립적으로 금덩이가 있을 수도 있고 없을 수도 있으므로, $2^k$개의 금 배치 중 모든 메모와 일치하며 도로 전체에 적어도 하나의 금덩이가 있게 하는 배치가 몇 개인지 알아내고자 한다. 출력값은 매우 큰 수가 될 수 있으므로, 결과를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지만 출력하면 된다.

제한

메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$의 각 문자는 < (작음), = (같음), > (큼), o (소문자 o), 또는 . (마침표) 중 하나이다. $1$ 이상이며, $\mathbf{S}$의 모든 문자가 . (마침표)인 것은 아니다.

테스트 세트 1 (공개 판정)

시간 제한: 20초. $\mathbf{S} \le 100$의 길이는 $2 \le$.

테스트 세트 2 (비공개 판정)

시간 제한: 40초. $\mathbf{S} \le 5 \times 10^5$의 길이는 $2 \le$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄에는 하나의 테스트 케이스를 나타내는 문자열 $\mathbf{S}$가 주어진다. $\mathbf{S}$의 $i$번째 문자는 위에서 설명한 코드를 사용하여 서쪽에서 동쪽으로 도로의 $i$번째 킬로미터에 대한 메모의 표시를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 메모와 일치하는 서로 다른 금 배치의 수를 소수 $10^9+7$ ($1000000007$)로 나눈 나머지이다.

예제 케이스 #1에는 유효한 배치가 세 가지 있으며, 각각 도로 oo<=>o<, oo<=>oo, o<<=>>o을 만든다.

예제 케이스 #2에는 유효한 배치가 없다.

예제 케이스 #3에서 유일하게 유효한 배치는 도로 o=o을 만든다. 유효한 배치는 항상 도로에 적어도 하나의 금덩이가 있도록 해야 한다는 점에 유의한다.

예제 케이스 #4에서는 $2^{17}$개의 배치가 모두 유효하다. 이 경우 미지의 (.)개 위치를 모두 비워 두도록(금덩이를 두지 않도록) 선택한 배치도 유효한데, 그러한 배치에서도 도로 전체에는 여전히 금덩이가 하나 있기 때문이다.