28687번 - 재우의 Pass를 사수하라!

문제

재우는 결국 지난 <제2회 고려대학교 MatKor Cup: 2023 Winter> 대회의 수영 과목에서 F를 막지 못했다. 이에 절치부심하여 이번 학기의 볼링 수업에서는 반드시 Pass를 받기로 다짐했다. 볼링은 10ドル$개의 프레임으로 이루어져 있다. 볼링의 규칙과 점수 계산 방식은 다음과 같다.

<규칙>

• 프레임은 1ドル$번 프레임부터 10ドル$번 프레임까지 순서대로 진행한다.
• 각 프레임이 시작될 때 10ドル$개의 핀이 내려온다.
• 1ドル$번부터 9ドル$번 프레임은 최대 두 번의 투구(投球)가 이루어진다.
  • 만약 첫 번째 투구에서 10ドル$개의 핀을 모두 넘어뜨리면 스트라이크가 되고, 두 번째 투구를 하지 않는다.
  • 첫 번째 투구에서 모두 넘어뜨리지 못했을 경우 남은 핀들로 두 번째 투구를 진행한다.
    • 두 번째 투구에서 남은 핀들을 모두 넘어뜨리면 스페어 처리가 된다.
    • 만약 두 번째 투구에서 남은 핀들을 모두 넘어뜨리지 못해도 다음 프레임으로 넘어가며 핀이 다시 10ドル$개로 초기화된다.
• 10ドル$번 프레임은 최대 3ドル$번의 투구를 한다.
  • 첫 번째 투구에 스트라이크를 치거나 두 번째 투구에 스페어를 치면 세 번째 투구를 할 수 있으며, 세 번째 투구 이후에는 경기가 종료된다.
  • 또한 스페어나 스트라이크를 치는 즉시 10ドル$개의 핀이 초기화 되어 내려온다.
    • 만약 첫 번째 투구에 스트라이크를 친다면 10ドル$개의 핀이 초기화되어 내려오고, 두 번째 투구 역시 스트라이크를 친다면 다시 10ドル$개의 핀이 초기화되어 내려와 세 번째 투구를 할 수 있다.
    • 만약 첫 번째 투구에 스트라이크를 치고, 두 번째 투구에 스트라이크를 치지 못해 핀이 남으면, 세 번째 투구는 남은 핀들로 진행한다.
    • 만약 첫 번째 투구에 스트라이크를 치지 못하면, 두 번째 투구는 남은 핀으로 하며, 여기서 스페어 처리를 하면 다시 10ドル$개의 핀이 초기화되어 내려와 세 번째 투구를 할 수 있다.
    • 만약 첫 번째 투구에 스트라이크를 치지 못하고, 두 번째 투구에도 스페어 처리를 하지 못하면 세 번째 투구 없이 경기가 종료된다.
  • 마지막 프레임의 세 번째 투구 이후에는 남은 핀에 관계 없이 경기가 종료된다.
• 10ドル$개를 모두 넘어뜨렸을 때 스트라이크와 스페어의 구분은 해당 투구 직전 10ドル$개의 핀이 내려왔다면 스트라이크, 해당 투구 직전 투구 이후 핀이 내려오지 않았다면 스페어다.

<점수 계산 방식>

• 볼링의 점수 계산 방식은 프레임별로 얻은 점수의 총합이다.
• 각 프레임에서 얻은 점수는 “핀 점수”와 “보너스 점수”의 합이다.
  • 핀 점수는 해당 프레임의 모든 투구에서 넘어진 핀 개수의 총합이다.
  • 보너스 점수는 10ドル$번 프레임에는 존재하지 않으며, 1ドル$번부터 9ドル$번 프레임까지에 대해서도 해당 프레임에 스페어나 스트라이크를 쳤을 경우만 보너스 점수가 존재한다.
    • 만약 해당 프레임에 스페어를 쳤다면 다음 프레임의 첫 번째 투구에서 넘어진 볼링 핀의 개수가 보너스 점수가 된다.
    • 만약 해당 프레임에 스트라이크를 쳤다면 다음 프레임에서 첫 번째 투구와 두 번째 투구에서 넘어진 핀의 총개수가 보너스 점수가 된다. 만약 첫 번째 투구가 스트라이크이고 두 번째 투구를 하지 않았다면 일반적인 볼링에서는 다음 프레임으로 넘어가지만, 이 문제에서는 보너스 점수를 다음 프레임으로 넘기지 않고 10ドル$점으로 처리한다.

재우가 볼링 수업에서 Pass를 받기 위해 스코어보드 사진을 찍어 가야 한다고 한다. 재우가 사진을 찍을 때 사진이 흔들리는 바람에 일부 점수가 보이지 않는다. 스코어보드에는 투구별 결과가 적혀있다.

각 투구 결과와 프레임별 점수 중 일부가 주어질 때, 최종적으로 $M$점이 되는 경우의 수를 10ドル^9+7$로 나눈 나머지를 구해보자. 스코어보드에 표시되는 결과가 하나라도 다른 경우 다른 경우의 수로 센다.

입력

첫 줄에 1ドル$번부터 10ドル$번 프레임에 대해 한 줄에 한 프레임씩 각 투구의 정보가 아래 방식으로 길이 21ドル$의 문자열 하나로 주어진다. 이때, 10ドル$번 프레임의 세 번의 투구는 스코어보드에서 모두 투구 내용이 보인다. 즉, 마지막 세 문자는 ?가 아니다.

• 스코어보드에서 투구의 내용이 보이지 않을 때 : ?
• 스코어보드에서 투구의 내용이 보일 때
  • 스트라이크를 친 경우 : X
  • 스페어 처리한 경우 : /
  • 해당 투구를 하지 않은 경우 : .
  • 0ドル$개의 핀이 넘어간 경우 : -
  • $i$(1ドル\le i\le 9$)개의 핀을 넘긴 경우 : $i$

만약 투구에 대한 정보로 가능한 경우가 겹치면, 더 위의 정보를 준다. 예를 들어 두 번째 투구에서 남아 있는 2ドル$개의 핀을 넘겨 스페어 처리한 경우 2ドル$가 아닌 /가 주어진다.

다음 줄에 경우의 수를 구하고 싶은 점수의 개수 $S=221$가 주어진다.

다음 줄에 점수를 검사하고 싶은 점수 $M_i = i(i =0, 1, 2, \cdots, S)$가 순서대로 공백으로 구분되어 주어진다.

예제의 입력은 $S\ne 221$이며 $M_i \ne i$이나, 이는 단순 사용자 테스트용으로 채점되지 않는다. 실제 입력은 $S = 221$이며 $M_i = i$인 경우만 주어진다.

출력

첫 줄에 $M=M_0(=0)$ 부터 $M=M_S(=S-1=220)$점 까지 해당 스코어 보드에서 최종적으로 $M$점이 되는 경우의 수를 10ドル^9+7$로 나눈 나머지를 공백으로 구분하여 출력한다.

주어진 스코어보드가 불가능한($M$점이 되는 경우의 수가 0ドル$인 것과는 다르다) 경우는 주어지지 않는다.

예제의 입력은 $S\ne 221$이며 $M_i \ne i$이나, 실제 입력은 $S = 221$이며 $M_i = i$이므로, 사용자가 제출할 때는 221ドル$개의 정수를 출력해야 한다.

제한

힌트