CF319A Malek Dance Club

作为传统，在每年 IOI 之前，Natalia Fan Club 的所有成员都会被邀请到 Malek Dance Club 共度一个愉快的夜晚。Malek Dance Club 有 $2^n$ 名成员，巧合的是，Natalia Fan Club 也有 $2^n$ 名成员。每个 MDC 的成员都被分配了一个唯一的编号 $i$，范围从 $0$ 到 $2^n-1$。NFC 的每个成员同样如此。 这个传统活动之一是一对一舞蹈，每个 MDC 的成员将与 NFC 的某个成员搭档跳舞。一个舞伴对是一对数字 $(a, b)$，表示编号为 $a$ 的 MDC 成员与编号为 $b$ 的 NFC 成员搭档。 搭配的复杂度被定义为所有满足 $a < c$ 且 $b > d$ 的舞伴对 $((a, b), (c, d))$ 的对数。 现在给你一个长度为 $n$ 的二进制数 $x$。我们已知编号为 $i$ 的 MDC 成员会与编号为 $i \operatorname{XOR} x$ 的 NFC 成员搭档。你的任务是计算该舞蹈搭配的复杂度，对 $1000000007$ 取模。 表达式 $y = i \operatorname{XOR} x$ 表示对 $i$ 和 $x$ 进行按位异或运算。这种操作在所有现代编程语言中都存在，例如 C++ 和 Java 表示为 «^», Pascal 中表示为 «xor»。

输入的第一行包含一个长度为 $n$ 的二进制数 $x$，满足 $1 \leq n \leq 100$。 该数字可能包含前导零。

输出所给舞伴分配方案的复杂度，对 $1000000007$ 取模。

由 ChatGPT 5 翻译