附加文件

题目描述

在很久很久以前的洛谷题库中，有这样一道题：给定 $n$ 个 01 串，问将这 $n$ 个 01 串插入到一个仅有根节点的 trie 后，这个 trie 的节点数是多少。

在本题中，将一个 01 串插入到一个 trie 定义为：

• 初始时，当前节点为根
• 从前往后遍历这个 01 串的所有字符
• 如果当前节点没有与此 01 字符对应的儿子，那么新建一个节点作为对应的儿子
• 然后将当前节点修改为对应的儿子

例如：将 000，010 插入到一个仅有根节点的 trie 后，这个 trie 的节点数为 6。

由于年代久远，这题的测试数据遭到了损坏：其中一些字符无法确定是 0 还是 1。 我们将这些损坏的字符记为 ?。

为了完全覆盖测试数据的所有情况，你需要求出所有可能的 $2^k$（$k$ 为 ? 的个数）种情况下的最终 trie 的节点数之和。

由于答案可能很大，你只需要输出答案对 998244353 取模的结果即可。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个仅包含 0、1、? 三种字符的字符串 $s_i$

输出格式

一行一个整数，表示答案

样例

样例输入 1

5
00110
01101
10011
11101
11111

样例输出 1

21

样例输入 2

3
?
0?
?1?

样例输出 2

88

数据范围与提示

本题共 $10$ 个测试点，每个测试点分值为 $10$。

测试点具体限制如下：

• 对于测试点 1，$s_i$ 中没有 ?
• 对于测试点 2, 3，$s_i$ 中没有 0 或 1
• 对于测试点 4，$n \le 8$
• 对于测试点 5，$n \le 12$
• 对于测试点 6，$n \le 16$
• 对于测试点 7,8,9,10，没有特殊限制。
• 对于所有数据：$1 \le n \le 20, 1 \le |si| \le 100$