노노그램

노노그램은 직사각형 격자를 규칙에 맞게 색칠하는 퍼즐 게임이다. 격자의 각 행과 열에는 양의 정수의 배열이 힌트로 주어지는데, 이는 각 행 또는 열에서 연속한 칠해진 칸의 배열을 나타낸다.

예를 들어 위의 왼쪽 그림을 보자. 4행에 있는 힌트 $\[10]$은 해당 행에서 연속한 $10$칸을 색칠해야 함을 나타낸다. 색칠할 $10$칸은 아무 곳에서나 시작해도 되고, 그 외의 칸은 비워 놔야 한다.

이번에는 9행에 있는 힌트 $\[3,4,4]$에 주목하자. 이는 해당 행에서 순서대로 $3$칸, $4$칸, $4$칸의 연속한 칸을 색칠해야 함을 나타낸다. 힌트의 순서와 칠해진 칸의 순서는 일치해야 하며, 각 연속한 칠해진 칸 사이에는 하나 이상의 빈 칸이 있어야 한다.

이해를 돕기 위해 위의 오른쪽 그림에는 4행과 9행만 남겨 두었다.

윤이는 노노그램을 풀면서 반드시 색칠해야 하는 칸과 비워 둬야 하는 칸 몇 개를 알아냈지만, 더 이상 진행이 되지 않아 애를 쓰고 있다. 방법을 고민하던 윤이는 문득 어떤 행 하나에 대해서 조건에 맞게 색칠하는 경우의 수가 궁금해졌다. 행의 힌트와 행의 각 칸에 대해 윤이가 알아낸 정보가 주어지면, 해당 행을 조건에 맞게 색칠하는 경우의 수를 구하시오.

첫 번째 줄에 행의 길이 $N$과 힌트 배열의 길이 $K$가 공백으로 구분되어 주어진다. ($1\le K\le N\le 3\ 000$)

두 번째 줄에 힌트를 나타내는 $K$개의 정수가 공백으로 구분되어 주어진다. 각 정수는 $1$ 이상 $N$ 이하이다.

세 번째 줄에 행의 정보를 나타내는 길이 $N$의 문자열이 주어진다. 문자열은 ‘.’, ‘O’, 또는 ‘X’로 이루어져 있으며, ‘.’은 아직 정보를 얻지 못한 빈 칸, ‘O’는 반드시 색칠해야 하는 칸, ‘X’는 반드시 비워 둬야 하는 칸을 나타낸다.

조건에 맞게 행을 색칠하는 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

본문에 제공된 노노그램의 출처는 이곳이다. https://www.nonograms.org/nonograms/i/28098