← 返回题目列表

Codeforces · 850/E

E. 随机选举

中文机器翻译题面 查看原题

贝尔兰德明年将举行总统选举!每个人都对此感到非常兴奋!

到目前为止,共有三位候选人,Alice、Bob 和 Charlie。

Bearland 有 n 个公民。选举结果将决定熊地所有公民多年的生活。由于这一重大责任,n 个公民中的每一个都会独立于其他选民,统一随机地在 Alice、Bob 和 Charlie 之间的六个优先顺序中选择一个。

Bearland 政府设计了一项功能,根据选民的偏好帮助确定选举结果。更具体地说,该函数为 $$f(x_{1},x_{2},\ldots,x_{n}):\{0,1\}^{n}\to\{0,1\}$$(接受 n 个布尔数并返回一个布尔数)。该函数还遵循以下属性:f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)。

每对候选人之间将进行三轮:Alice 和 Bob、Bob 和 Charlie、Charlie 和 Alice。在每一轮中,如果第 i 个公民在本轮中更喜欢第一个候选人而不是第二个候选人,则 xi 将等于 1,否则为 0。之后,将计算 y = f(x1, x2, ..., xn)。如果 y = 1,则第一个候选人将被宣布为本轮获胜者。如果 y = 0,则第二个将分别获胜。

定义候选人赢得两轮的概率为 p。 p·6n 始终是整数。打印该整数模 109 + 7 = 1 000 000 007 的值。

输入

第一行包含一个整数 n (1 ≤ n ≤ 20)。

下一行包含长度为 2n 的 0 和 1 字符串,表示函数 f。设 bk(x) 是 x 的二进制表示形式中的第 k 位,该字符串的第 i 个(从 0 开始)数字表示 f(b1(i), b2(i), ..., bn(i)) 的返回值。

对于任何 x1、x2、ldots、xn 值,保证 f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)。

输出

输出一个整数——问题的答案。

示例

输入 #1

3
01010101

输出 #1

216

输入 #2

3
01101001

输出 #2

168

注意

在第一个样本中,结果始终完全由第一位投票者决定。换句话说,f(x1, x2, x3) = x1。因此,无论发生什么,都会有一个候选人赢得两轮胜利(更具体地说,是位于选民 1 偏好列表顶部的候选人),因此 p = 1,我们打印 1·63 = 216。