福克斯·夏尔正在学习数论。 她认为一个非负非空集合 $S$ 是完美的，当且仅当对于任意的 $a,b\in S$（注意这里 $a$ 可以等于 $b$），都有 $a\bigoplus b\in S $。其中，$\bigoplus $ 代表异或运算，详见[百度百科](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677)。 请计算以小于等于 $k$ 的非负整数构成的完美集合的个数。这个答案可能会很大，所以请对 $1000000007\ (10^9+7)$ 取模。

第一行包含一个整数 $k\ (0\le k\le 10^9)$。

输出一个整数，表示完美集合的个数对 $1000000007\ (10^9+7)$ 取模后的值。

在样例 1 中，有两个满足条件的集合：$\{0\}$ 和 $\{0,1\}$。然而，集合 $\{1\}$ 并不是完美集合，因为 $1\bigoplus1=0$，而集合 $\{1\}$ 中并不包含元素 $0$。 在样例 4 中，有 6 个满足条件的集合：$\{0\},\{0,1\},\{0,2\},\{0,3\},\{0,4\},\{0,1,2,3\}$。