字典树

题目描述 对于 � 个 01 字符串 �� ，定义他们的权值是这 � 个 �� 的串插入一个空的 Trie 树后得 到的结果 Trie 中的节点个数。例如 [01,00] 的权值是 4，[010,1] 的权值是 5。

现在给出了 � 个只包含 01? 的字符串 �� 。其中 ? 表示既有可能是 0 也有可能是 1。 显然，如果有 � 个 ?，那么一共有 2� 个可能的字符串集合。

现在想要知道对于这 2� 种状态，权值的和是多少，对109 + 7 取模。

输入格式 第一行一个整数 � 表示字符串数量。

接下来 � 行每行一个只包含 01? 的字符串 �� 。

输出格式 输出一个数，表示答案。

样例输入 1 3 01 ??1 1

样例输出 1 23

样例输入 2 5 ??? ??? ??? ??? ???

样例输出 2 651526144

样例输入输出 3 见下发文件。

数据规模 共 10 个测试点。 测试点 1,2 满足� ≤ 10。

测试点 3,4 满足� ≤ 20。

测试点 5,6 满足� ≤ 5。

测试点 7,8 满足� ≤ 10。

对于所有数据，满足 1 ≤ � ≤ 20,1 ≤ �� ≤ 50。