카드 색칠 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$
• 주어지는 모든 수는 정수이다.