作为一项传统,每年 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