#P5451. 字符串

    ID: 4457 传统题 1000ms 256MiB 尝试: 81 已通过: 25 难度: 8 上传者: 标签>CF2400提高+/省选-对称性分析AC 自动机失败链接贡献汇总AC 自动机 DP状压 DP滚动数组

字符串

Description

给定正整数m以及n个01串s1~sn,

你需要求出长度为2m的反对称的包含这n个01串作为子串的01串的个数。

对998244353取模。

一个01串s是反对称的当且仅当它对于1<=i<=|s|都满足s[i]≠s[|s|-i+1]。

Format

Input

第一行两个整数n,m。

接下来n行每行一个字符串s1~sn。 n<=6,|si|<=100,m<=500。

Output

一行一个整数表示答案。

Samples

2 3
011
001
4