题目描述

给定一个正整数$L$，以二进制表示。 有多少对非负整数$(a,b)$满足以下条件?

• $a+b \leq L$
• $a+b = a\ XOR\ b$

由于满足条件的对数可能非常多，输出答案模 $10^9十7$。

什么是异或运算(XOR)?

两个整数 $A$ 和 $B$ 的异或运算 $A\ XOR\ B$ 定义如下:

• 当二进制形式的 $A$和 $B$进行异或运算时，每一位的值由以下规则确定:

• 如果 $A$和 $B$ 同时在该位上是 1 或同时是 0结果为 0;

• 如果 $A$ 和 $B$ 在该位上只有一个是 1，结果为 1。

• 例如，$3\ XOR\ 5=6$。(换算成二进制:$011\ XOR\ 101=110$。)

输入

输入一个整数$L$

输出

输出满足条件的对数$(a,b)$的个数,结果模$10^9+7$

10

5

样例解释

满足条件的五个对数是:$(0,0),(0,1),(1,0),(0,2)$和$(2,0)$

1111111111111111111

162261460

提示

$1 \leq L \leq 2^{100001}$