아주아주 오래전(무려 7년 전), 당신은 동남아시아 어딘가에 있는 서-동 방향의 길 위에 있었고, 그 길에는 금 덩어리(gold nugget)가 적어도 하나는 존재한다고 알려져 있었다. 당신은 제한적이지만 믿을 수 있는 금 탐지기를 가지고 있었다. 그 금으로 엄청나게 부자가 된 후, 당신은 가능한 모든 활동을 해 보았지만 결국 지루해졌다. 거대한 저택을 배회하던 중, 그 금 채굴 여정 때의 메모를 발견했다.

그 메모는 길의 도식(diagram) 형태이다. 길의 각 1km 구간마다 다음 5가지 표시 중 하나가 적혀 있다.

<: 가장 가까운 금 덩어리가 서쪽에 있음을 의미한다.
=: 동쪽과 서쪽에 있는 가장 가까운 금 덩어리까지의 거리가 같고, 해당 위치에는 금 덩어리가 없음을 의미한다.
>: 가장 가까운 금 덩어리가 동쪽에 있음을 의미한다.
o: 해당 위치에 금 덩어리가 있음을 의미한다.
.: 해당 위치에 대해 아무 것도 알려져 있지 않음을 의미한다.

.로 표시된 k개의 미지의 위치는 각각 독립적으로 금 덩어리가 있을 수도 없을 수도 있으므로, 가능한 금 배치의 수는 2^k가지이다. 이 중에서 메모의 모든 내용과 모순되지 않으면서, 또한 길 전체에 금 덩어리가 적어도 하나 존재하도록 하는 배치의 수를 구하라. 출력값이 매우 클 수 있으므로, 답을 소수 10^9+7(1000000007)로 나눈 나머지를 출력하라.

#10466 upload 1 done 1 how_to_reg 1

Old Gold timer 20s memory 2048MB

#10466

Old Gold 20s 2048MB