문제

논리 연산이란 참을 나타내는 논리값 1 과 거짓을 나타내는 논리값 0 을 다루는 연산을 말합니다. 이 문제에서는 다음의 두 가지 논리 연산자가 등장합니다.

• 논리합 (|, OR): 양쪽의 두 값 중 한쪽이라도 1 이라면 연산의 결과는 1 입니다. 그렇지 않다면 연산의 결과는 0 입니다. 예시는 다음과 같습니다.

-   **`0|0`** = **`0`**

-   **`0|1`** = **`1`**
-   **`1|0`** = **`1`**
-   **`1|1`** = **`1`**

• 논리곱 (&, AND): 양쪽의 두 값이 모두 1 이라면 연산의 결과는 1 입니다. 그렇지 않다면 연산의 결과는 0 입니다. 예시는 다음과 같습니다.

-   **`0&0`** = **`0`**

-   **`0&1`** = **`0`**
-   **`1&0`** = **`0`**
-   **`1&1`** = **`1`**

이때, 논리값 개와 논리 연산자 개가 번갈아서 등장하는 문자열을 길이 의 논리식이라고 부릅니다. 모든 논리식은 대응되는 하나의 논리값을 가지며, 이는 다음과 같이 구할 수 있습니다.

1. 먼저, 논리식에 등장하는 논리곱 연산자 각각에 대해 양쪽의 두 값과 연산자를 지우고 해당하는 연산의 결과로 교체합니다.
2. 다음, 논리식에 등장하는 논리합 연산자 각각에 대해 양쪽의 두 값과 연산자를 지우고 해당하는 연산의 결과로 교체합니다.

이때 하나의 논리식에 같은 논리 연산자가 여러 번 등장한다면 그중 맨 왼쪽부터 순서대로 연산을 수행합니다.

예를 들어 논리식 0&1&1|0|1|1&1 에 대해 다음과 같이 대응되는 논리값을 구할 수 있습니다.

• 0&1&1|0|1|1&1
• 0&1|0|1|1&1 (0&1 을 0 으로 교체합니다.)
• 0|0|1|1&1 (0&1 을 0 으로 교체합니다.)
• 0|0|1|1 (1&1 을 1 로 교체합니다.)
• 0|1|1 (0|0 을 0 으로 교체합니다.)
• 1|1 (0|1 을 1 로 교체합니다.)
• 1 (1|1 을 1 로 교체합니다.)

따라서 0&1&1|0|1|1&1 에 대응되는 논리값은 1 입니다.

여러분이 해결해야 하는 문제는 다음과 같습니다.

여러분에게 길이 의 문자열이 주어집니다. 이 문자열은 다음 조건을 만족합니다.

• 홀수 에 대해, 번째 문자는 '0', '1', '?' 중 하나입니다.
• 짝수 에 대해, 번째 문자는 '|', '&', '?' 중 하나입니다.

여러분은 이 문자열에 대해 다음 동작을 번 수행해야 합니다.

• 이상 이하의 정수 와 문자 가 주어질 때, 문자열의 번째 문자를 로 바꿉니다. 문자를 바꾼 후에도 문자열은 위의 조건을 항상 만족합니다.

이때 각 동작 후 논리식의 상태는 유지됩니다. 예를 들어 한 번의 동작으로 문자열 "0&??1|0|1|1&1"이 "0&??1|0|0|1&1"으로 바뀌었을 경우 그다음 동작은 문자열 "0&??1|0|0|1&1"에 수행합니다.

동작을 번 수행하면서, 각 동작 이전과 이후에 문자열에서 '?'를 각각 적절한 문자로 바꾸어 대응되는 논리값이 1인 올바른 논리식으로 만드는 방법의 가짓수를 구하는 프로그램을 작성해 주세요. 단, 정답이 매우 클 수 있으니 정답을 으로 나눈 나머지를 구해 주세요.

입력

첫 번째 줄에 테스트 케이스의 개수 가 주어집니다.

그다음 줄부터 개의 테스트 케이스가 주어집니다. 테스트 케이스의 형식은 다음과 같습니다.

첫 번째 줄에는 두 정수 과 가 공백으로 구분되어 주어집니다.

두 번째 줄에는 길이 의 논리식이 공백 없이 주어집니다.

그다음 줄부터 개의 줄에 각각 수행해야 하는 동작을 나타내는 정수 와 문자 가 공백으로 구분되어 주어집니다.

출력

각 테스트 케이스에 대해 새로운 줄에 개의 정수를 공백으로 구분해 출력합니다. 출력해야 하는 정수는 다음과 같습니다.

• 첫 번째로 출력할 정수는 처음 주어진 문자열에 대한 정답을 으로 나눈 나머지입니다.
• 일 때, 번째로 출력할 정수는 번째 동작 후의 정답을 으로 나눈 나머지입니다.

제한

• 모든 테스트 케이스에서 의 합은 을 초과하지 않습니다.
• 모든 테스트 케이스에서 의 합은 을 초과하지 않습니다.
• 홀수 에 대해, 번째 문자는 항상 '0', '1', '?' 중 하나입니다.
• 짝수 에 대해, 번째 문자는 항상 '|', '&', '?' 중 하나입니다.

서브태스크

노트

첫 번째 테스트 케이스에서, 처음 주어진 문자열은 "???"입니다. 정답을 구할 개의 문자열과 대응되는 설명은 다음과 같습니다.

1. "???": 논리값 1 에 대응되는 논리식 0|1, 1|0, 1|1, 1&1 을 만들 수 있습니다. 정답은 입니다.
2. "?|?": 논리값 1 에 대응되는 논리식 0|1, 1|0, 1|1 을 만들 수 있습니다. 정답은 입니다.
3. "?&?": 논리값 1 에 대응되는 논리식 1&1 을 만들 수 있습니다. 정답은 입니다.
4. "???": 논리값 1 에 대응되는 논리식을 만들 수 없습니다. 정답은 입니다.
5. "0??": 논리값 1 에 대응되는 논리식 0|1 을 만들 수 있습니다. 정답은 입니다.