어려운 조각 프로젝트

문제 지문은 이전 문제와 거의 같으며, 몇 문장이 굵게 표시된 부분만 바뀌었다.

어릴 적부터 조각가였던 다빈치는 많은 조각을 설계했지만, 완성된 것은 거의 없었고 그중 웃는 아기를 안은 성모 하나만이 남았다. 이 조각을 완성하는 데 다빈치는 오랜 시간과 많은 재료를 들였다.

다빈치는 이 프로젝트의 첫 단계에 n일을 쓰기로 계획했다. 처음에 다빈치에게는 조각할 재료가 없었다. 매일 그는 휴일을 보내며 시장에 가서 재료 1단위를 사거나('o'로 표시), 조각 작업을 하며 재료 1단위를 소비했다('w'로 표시). 그런데 일정을 짜고 나서 다빈치는 이것이 현실적이지 않다는 것을 깨달았다. 어떤 작업일에는 재료가 없어서 아무것도 못 할 수도 있고, 끝날 때 쓰지 않은 재료가 남을 수도 있었다. 조각 프로젝트를 순조롭게 진행하기 위해 다빈치는 특정 날의 활동을 취소하기로 했으며, 조건은 다음과 같다.

1. 재료 없이 시작해서, 다빈치는 각 작업일에 조각할 재료를 최소 1단위 가지고 있어야 한다.
2. n일이 지난 뒤 다빈치에게 남는 재료가 없어야 한다.
3. 취소하는 활동의 수가 최소가 되어야 한다. (다빈치는 원래 일정을 너무 많이 바꾸고 싶지 않았다!)

다빈치는 이 조건을 만족하도록 최소한의 활동을 취소하는 방법의 수를 알고 싶어 한다. 어떤 일정에서 취소된 활동이 하나라도 다른 일정에서는 유지된다면, 두 일정은 서로 다른 것으로 본다.

첫 줄에는 파일에 들어 있는 입력 데이터 세트의 수 1 ≤ K ≤ 10이 주어진다. 이어서 K개의 데이터 세트가 다음 형식으로 주어진다.

각 데이터 세트는 다빈치의 원래 일정을 나타내는 비어 있지 않은 문자열 S 한 줄로 주어진다. S의 길이는 최대 1000이며 'w'와 'o'로만 이루어져 있다. S의 길이를 읽어 n을 구할 수 있다.

각 데이터 세트마다 먼저 “Data Set x:”를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호다.

그다음 일정을 실행 가능하게 만들기 위해 최소한의 활동을 취소하는 방법의 수를 출력한다. 답이 매우 클 수 있으므로 10^9 + 7로 나눈 나머지를 출력한다.

각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.