题目描述

对于 $n$ 个 01 字符串 $s_i$，定义他们的权值是这 $n$ 个 $s_i$ 的串插入一个空的 Trie 树后得 到的结果 Trie 中的节点个数。例如 [01,00] 的权值是 4，[010,1] 的权值是 5。 现在给出了 $n$ 个只包含 $01?$ 的字符串 $s_i$。其中 $?$ 表示既有可能是 $0$ 也有可能是 $1$。 显然，如果有 $K$ 个 $?$，那么一共有 $2^K$ 个可能的字符串集合。 现在想要知道对于这 $2^K$ 种状态，权值的和是多少，对$10^9 + 7$ 取模。

输入格式

第一行一个整数 $n$ 表示字符串数量。 接下来 $n$ 行每行一个只包含 $01?$ 的字符串 $s_i$。

输出格式

输出一个数，表示答案。

3
01
??1
1

23

5
???
????
?????
??????
???????

651526144

样例输入输出 3

见下发文件。

数据规模

共 10 个测试点。

测试点 1,2 满足$K ≤ 10$。

测试点 3,4 满足$K ≤ 20$。

测试点 5,6 满足$n ≤ 5$。

测试点 7,8 满足$n ≤ 10$。

对于所有数据，满足$1 ≤ n ≤ 20,1 ≤ |s_i| ≤ 50$。

附件

附件下载