LaLa와 마법석

어느 날 \color{blue}{\text{LaLa}}는 마법 도구에 쓰는 마법석 부품이 다 떨어졌다는 것을 알았다. (이 부품은 우리 세계의 배터리와 같다.) 그래서 \color{blue}{\text{LaLa}}는 근처 가게에 달려가 마법석 판 한 장을 샀다.

\color{blue}{\text{LaLa}}는 이 판을 마법석 부품으로 잘라 쓰려고 한다. 판은 $N \\times M$ 칸으로 이루어져 있다. 그런데 일부 칸은 \color{blue}{\text{LaLa}}의 마법 도구와 맞지 않는다.

필요한 마법석 부품은 7칸짜리 U자 모양 조각이다.

접착제를 사지 않았기 때문에 작은 조각들을 이어 붙여 필요한 모양을 만들 수는 없다.

또한 \color{blue}{\text{LaLa}}는 마법석 낭비를 싫어한다. 그래서 호환되는 칸이 모두 필요한 모양 중 하나에 속하도록 판을 잘랐을 때만 만족한다.

\color{blue}{\text{LaLa}}가 만족하는 판의 절단 방법 수를 $998\\,244\\,353$으로 나눈 나머지로 구하는 프로그램을 작성하라. 두 절단 방법이 다른 것은, 호환되는 두 칸이 한 방법에서는 같은 부품에 속하고 다른 방법에서는 서로 다른 부품에 속하는 경우가 존재할 때뿐이다.

입력은 다음 형식으로 주어진다.

$N$ $M$

$S\\_0$

$S\\_1$

$\\vdots$

$S\\_{N-1}$

여기서 $N$은 판의 행 수, $M$은 열 수이다. $S\\_i$는 길이 $M$의 이진 문자열이며, 위에서 $i$번째 행, 왼쪽에서 $j$번째 열의 칸이 호환되지 않는 경우에만 $j$번째 문자가 '1'이다.

입력은 다음 제약을 만족한다.

• $N$과 $M$은 정수이다.
• $3 \\le N, M \\le 1\\,000$

\color{blue}{\text{LaLa}}가 만족하는 절단 방법의 수를 $998\\,244\\,353$으로 나눈 나머지를 출력한다.

첫 번째 예시에서 판을 자르는 가능한 두 가지 방법은 다음과 같다.

두 번째 예시에서 판을 자르는 방법은 다음 하나뿐이다.