← 返回题目列表

Codeforces · 319/A

A. 马利克舞蹈俱乐部

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

作为一项传统,每年 IOI 之前,Natalia 粉丝俱乐部的所有成员都会被邀请到 Malek 舞蹈俱乐部一起度过一个有趣的夜晚。 Malek Dance Club 有 2n 名成员,巧合的是 Natalia Fan Club 也有 2n 名成员。 MDC 的每个成员都被分配一个从 0 到 2n - 1 的唯一 id i。对于 NFC 的每个成员也是如此。

这一传统的一部分是一对一舞蹈,MDC 的每位成员与 NFC 的一名成员一起跳舞。舞蹈对是一对数字 (a, b),使得来自 MDC 的成员 a 与来自 NFC 的成员 b 跳舞。

配对分配的复杂度是满足 a < c 且 b > d 的跳舞对 (a, b) 和 (c, d) 的数量。

给定一个长度为 n 的二进制数,名为 x。我们知道来自 MDC 的成员 i 与来自 NFC 的成员 $$i \oplus x$$ 跳舞。您的任务是计算此作业的复杂度,以 1000000007 (109 + 7) 为模。

表达式 $$x \oplus y$$ 表示对数字 x 和 y 应用“XOR”。此操作存在于所有现代编程语言中,例如,在 C++ 和 Java 中表示为“^”,在 Pascal 中表示为“xor”。

输入

输入的第一行包含长度为 n 的二进制数 x,(1 ≤ n ≤ 100)。

该数字可能包含前导零。

输出

打印给定舞蹈分配模 1000000007 (109 + 7) 的复杂性。

示例

输入 #1

11

输出 #1

6

输入 #2

01

输出 #2

2

输入 #3

1

输出 #3

1