Malek Dance Club

题意翻译

有一个长度为 $n$ 的二进制串 $x$，要求将 $0$ 至 $2^n-1$ 的所有整数异或 $x$ ，求异或后产生的序列中逆序对的个数，**答案对 $\boldsymbol{{10}^9+7}$ 取模**。

题目描述

As a tradition, every year before IOI all the members of Natalia Fan Club are invited to Malek Dance Club to have a fun night together. Malek Dance Club has $ 2^{n} $ members and coincidentally Natalia Fan Club also has $ 2^{n} $ members. Each member of MDC is assigned a unique id $ i $ from $ 0 $ to $ 2^{n}-1 $ . The same holds for each member of NFC. One of the parts of this tradition is one by one dance, where each member of MDC dances with a member of NFC. A dance pair is a pair of numbers $ (a,b) $ such that member $ a $ from MDC dances with member $ b $ from NFC. The complexity of a pairs' assignment is the number of pairs of dancing pairs $ (a,b) $ and $ (c,d) $ such that $ a<c $ and $ b>d $ . You are given a binary number of length $ n $ named $ x $ . We know that member $ i $ from MDC dances with member  from NFC. Your task is to calculate the complexity of this assignment modulo $ 1000000007 $ $ (10^{9}+7) $ . Expression  denotes applying «XOR» to numbers $ x $ and $ y $ . This operation exists in all modern programming languages, for example, in C++ and Java it denotes as «^», in Pascal — «xor».

输入输出格式

输入格式

The first line of input contains a binary number $ x $ of lenght $ n $ , $ (1<=n<=100) $ . This number may contain leading zeros.

输出格式

Print the complexity of the given dance assignent modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

11

输出样例 #1

6

输入样例 #2

01

输出样例 #2

2

输入样例 #3

1

输出样例 #3

1