31037번 - 카드 색칠 2

영우는 송년대회 참가자들을 환영하기 위해 정성스럽게 송년대회 환영 카드를 만들었다. 입부 환영 카드에서 소환된 동현이의 환영이 참가자들을 환영할 것이다. 총 $N^2$개의 카드가 있고, 카드들은 가로 $N$행, 세로 $N$열의 정사각형 모양으로 배열되어 있다. 이환이는 환영 카드의 색칠을 맡았다. 이환이는 모든 카드들을 검은색 또는 하얀색으로 색칠할 것이다. 첫 행의 몇 개의 카드들은 이미 색칠되어 있다. 이때, 다음 규칙에 따라야 한다.

• 카드들의 색상 배치가 복잡해지는 것을 피하기 위해 한 카드와 그 카드의 바로 오른쪽 아래에 있는 카드는 색이 같아야 한다. 즉, $i$행 $j$열의 카드와 $i+1$행 $j+1$열의 카드 색은 같아야 한다. ($1 \le i, j <N$)
• 모든 행에 대해서 그 행을 이루는 하얀 카드의 수는 같아야 한다.

초기에 첫 행의 몇 개의 카드가 어떻게 색칠되어 있어도 규칙에 따라 카드들을 색칠하는 하나 이상의 방법이 있음을 증명할 수 있다.

카드 색칠이 완료된 이후, 카드 배열의 점수는 다음과 같이 정의된다.

• 각 카드가 하얀색인 경우 그 카드는 하나의 문양에 속하는데, 두 카드 사이를 상하좌우로 하얀색 카드만 경유하여 이동할 수 있는 경우에만 같은 문양에 속한다.
• 카드 배열의 점수는 서로 다른 문양의 수이다. 문양의 모양과는 상관없다.

이환이는 카드를 색칠할 때 나올 수 있는 카드 배열들의 점수가 궁금해졌다. 첫 행의 카드들의 색칠 여부가 주어질 때, 규칙에 맞게 카드를 색칠할 때 나올 수 있는 서로 다른 카드 배열들의 점수의 합을 구해 출력하는 프로그램을 작성하라. 단, 답이 너무 클 수 있으니 $998\,244\,353$으로 나눈 나머지를 출력하라.

첫째 줄에 정수 $N$이 주어진다.

둘째 줄에 0, 1, ?로 구성된 길이 $N$의 문자열이 주어진다. $i$번째 문자가 ?인 것은 1행 $i$열의 카드가 색칠되지 않았다는 것을 의미하고, 0 또는 1인 것은 1행 $i$열의 카드가 검은색, 흰색으로 색칠되었음을 의미한다.

첫째 줄에 규칙에 맞게 카드를 색칠할 때 나올 수 있는 서로 다른 카드 배열들의 점수의 합을 $998\,244\,353$으로 나눈 나머지를 출력하라.

• $3 \leq N \leq 1\,000\,000$
• 주어지는 모든 수는 정수이다.