Kuro와 위상 정렬 패리티

Kuro는 최근 "역대 가장 똑똑한 고양이" 대회에서 우승했다. 그러자 세 친구는 Kuro의 우승을 축하하기 위해 Katie의 집에 가기로 했다. 푸짐하게 식사한 뒤 잠시 쉬고 게임을 시작했다.

Kuro는 Katie에게 흰 종이 한 장, 연필 한 자루, 가위 한 자루와 많은 화살표만으로 게임을 만들라고 도전했다(화살표의 개수는 무한하다고 가정해도 된다). Katie는 즉시 위상 정렬 패리티라는 게임을 생각해 냈다.

종이는 1부터 n까지 번호가 매겨진 n개의 조각으로 나뉜다. Shiro는 일부 조각을 어떤 색으로 칠했다. 구체적으로, i-th번째 조각의 색은 $c_{i}$이며, $c_{i}$ = 0은 검은색을, $c_{i}$ = 1은 흰색을 나타내고, $c_{i}$ = -1은 그 조각이 아직 칠해지지 않았음을 뜻한다.

게임의 규칙은 간단하다. 플레이어는 서로 다른 일부 조각의 쌍 사이에 화살표를 놓아야 하며, 각 화살표가 시작하는 조각에 적힌 수는 화살표가 끝나는 조각에 적힌 수보다 작아야 한다. 또한 서로 다른 두 조각은 최대 하나의 화살표로만 연결할 수 있다. 그다음 플레이어는 칠해지지 않은 각 조각의 색(0 또는 1)을 선택해야 한다. 화살표를 놓고 조각에 색을 칠하는 유효한 방법의 점수는 색이 번갈아 나타나는 조각 경로의 개수로 정의한다. 예를 들어, [1 → 0 → 1 → 0], [0 → 1 → 0 → 1], $[1]$, $[0]$는 유효한 경로이므로 개수에 포함된다. 조각 x에서 조각 y로 향하는 화살표가 있을 때, 그리고 그럴 때에만 조각 x에서 조각 y로 이동할 수 있다.

하지만 Kuro는 아직 즐겁지 않다. 그는 패리티를 좋아한다. p = 0은 "짝수"를, p = 1은 "홀수"를 나타낼 때, 그가 좋아하는 패리티를 p라고 하자. 그는 점수의 패리티가 p가 되도록 화살표를 놓고 색을 선택하려 한다.

Kuro를 만족시키는 방법은 매우 많을 것 같다. 그는 그 개수를 세고 싶지만, 이는 매우 큰 수가 될 수 있다. 이 문제를 해결하도록 도와주되, 답을 $10^{9}$ + 7로 나눈 나머지를 출력하자.

첫째 줄에 조각의 개수와 Kuro가 원하는 패리티를 나타내는 두 정수 n와 p (1 ≤ n ≤ 50, 0 ≤ p ≤ 1)가 주어진다.

둘째 줄에 조각의 색을 나타내는 n개의 정수 $c_{1}$, $c_{2}$, ..., $c_{n}$ (-1 ≤ $c_{i}$ ≤ 1)가 주어진다.

색이 번갈아 나타나는 유효한 경로의 개수에 해당하는 패리티가 p가 되도록 화살표를 놓고 색을 선택하는 방법의 수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 아래 그림과 같이 조각에 색을 칠하고 화살표를 추가하는 방법이 6가지 있다. 왼쪽부터 오른쪽으로 첫째 행의 점수는 3, 3, 5이고 둘째 행의 점수는 5, 3, 3이다.