2017.8.22 ACM 训练赛

F. 沉陷过往的幻灭

单点时限: 2.0 sec

内存限制: 256 MB

对于给定的数 $a, b$ 求
$$\sum_{i=0}^{314159} a \; xor \; (b \; shl \; i)$$
其中 $shl$ 是左移,等同于 C 中的 << 运算符。

输入格式

共两行,每行一个二进制数,分别表示 $a, b$,长度都不超过 $10^5$,不带前导零,不会是零。

输出格式

输出一个数,答案可能很大,输出模 $10^9+7$ 后的结果。

样例

Input
10
1010
Output
489429555