4299. 学姐的下午茶

【题目背景】

Mami 的下午茶来了很多新客人，她决定做一些甜点招待客人们。

【题目描述】

具体的，Mami 准备了 $n$ 到新甜点，每个甜点的制作过程可以用 $01$ 字符串 $s_i$ 来表示。

Mami 喜欢在下厨前就记住所有菜品的制作过程，但是 Mami 并不喜欢记很多东西，所以她打算把这 $n$ 个 $s_i$ 插入到一颗字典树中。记 $cnt$ 为这个字典树中的节点数，她可以花费 $cnt$ 分钟来记住这个字典树来记住所有的甜点。

但是贪玩的贝贝不小心把咖啡打翻在菜谱上，导致这 $n$ 个字符串中有一些字符变成了 $?$。这些 $?$ 都有可能是 $1$ 或者 $0$。Mami 很头疼，她希望你告诉她所有可能的 $2^k$（$k$ 为 $?$ 的个数）种情况下的最终字典树的节点数之和

答案对 $10^9+7$ 取模。

在本题中，将一个 $01$ 串插入到一个字典树定义为：

1. 初始时，当前节点为根。

2. 从前往后遍历这个 $01$ 串的所有字符。

3. 如果当前节点没有与此 $01$ 字符对应的儿子，那么新建一个节点作为对应的儿子。

4. 然后将当前节点修改为对应的儿子。

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

【输入格式】

第一行一个整数 $n$。

接下来 $n$ 行，每行一个只包含 $0,1,?$ 的字符串。

【输出格式】

一行一个整数，表示答案

【样例输入1】

5
00110
01101
10011
11101
11111

【样例输出1】

21

【样例输入2】

3
?
0?
?1?

【样例输出2】

88

【数据规模与约定】

特殊性质：$s_i$ 中不含 $?$。

对于所有数据，满足 $n\le 20,|s_i|\le 100$。

大样例，所有大样例均无特殊性质。

【来源】

HihoCoder - 1646。