编程题：AN easy Concrete Mathematics question

Let the function $$sum(i)$$ means the number of $$1$$ in binary representation of $$i$$ (e.g. $$8$$ in binary is $$(1000)_2$$. There is a single $$1$$ in it. So $$sum(8)$$ is **1** ). Now we have an integer $$N$$, please calculate the answer of

$$\sum_1^n{sum\left( i \right)}$$

Please print the result mod by $$10^9+7$$
### Input format:
A single line: $$N$$ ($$N\le 10^8$$)

### Output format:
A single line: The result

### Input example:


in
10000000


### Output example:



out
114434632







答案：若无答案欢迎评论

以$$(1101000)_2$$为例，我们将它分成三个部分处理：

$$(0000001)_2——(1000000)_2$$

$$(1000001)_2——(1100000)_2$$

$$(1100001)_2——(1101000)_2$$

我们倒序去考虑三个区间（这样处理的原因是通过$$lowbit$$可以快速找到当前需要处理的区间并迭代），将这三个区间的$$Sum(i)$$分别求和。

那么每个区间怎么求和呢？我们称一个区间的终点为$$end$$（那么起点对应的就为$$end-lowbit(end)+1$$，显然），考虑将其分为$$lowbit(end)$$所包含的低位和$$lowbit(end)$$以上的高位两部分位分别考察他们的贡献。

> 例如，$$(1101000)_2$$就拆分为$$(1100000)_2$$和$$(0001000)_2$$

首先有引理1：当前区间的数字个数$$=lowbit(end)$$

其次有引理2：高位数字有$$popcount(end)-1$$个$$1$$

观察到由于高位部分不变，那么高位的贡献显然为$$(popcount(end)-1)*lowbit(end)$$

接下来考察低位部分，那么低位从形式上看就是$$000……001$$到$$100……000$$这样形式的一个数列求$$Sum(i)$$之和。这样考虑没有头绪，接下来考虑每一个二进制位，于是有引理3：

从$$0$$到$$2^i$$（$$i$$为任意正整数）的所有数的二进制表示，除最高位以外**每一个二进制位上都是均匀分布的**，也就是说，每一位在整个低位区间中，都有一半的情况是$$1$$。

利用这个引理，我们就知道低位表示中$$1$$的个数为$$lowbit(end)*低位位数/2+1$$。其中这个$$1$$是低位的左端那一个$$1$$。至于低位位数可以用$$popcount$$求。

这样，时间复杂度是$$O(logL)$$，在语言内置的所有整型范围内，甚至可以理解为是$$O(1)$$的。