Migrated from Lutece 1336 柱爷与三叉戟

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

柱爷作为智商街上的一哥，战斗力自然不弱，在瞄哈哈村也是数一数二的存在.

当然，柱爷还有一个身份，那就是守护者.

所谓守护者，是瞄哈哈村的一个特殊群体的称号，他们负责守卫我们世界的安全，因为每逢$772002$年，咸鱼王的军队便会趁世界屏障力量最低谷时，强行来到我们的世界进行烧杀抢掠，而首当其冲的，就是瞄哈哈村.

每逢这个时候，瞄哈哈村的守护者们便会站出来守护这一方土地！

柱爷的实力在守护者中也是最顶尖的存在，而柱爷的武器则是一把传奇三叉戟，据传，这是一位在$772002$年前陨落的强大守护者F91曾经使用过的12级灵能武器，拥有毁天灭地的力量.

三叉戟能在美德中汲取力量，保护同伴，痛击敌人，当然，在深海中，柱爷也能使用三叉戟.

而三叉戟的美德力量来源于神秘的自然数.

对于某个数$X$，定义$F[X]$为$X$二进制中$1$的数量，而$F(X)$，就是这个数的美德力量.

当然，强大的武器也有限制，对于传奇三叉戟来说，限制就是其巨大的灵能消耗！

三叉戟每发出一次强度为$N$的攻击，就会消耗在$[1,N]$中满足$F[i] > F[j]$的对数$(1 \leq i < j \leq N)$的灵能.

现在柱爷想考考你，当三叉戟打出一次强度为$N$的攻击时，会消耗多少的灵能？

Input

第一行一个整数$N$，表示三叉戟的攻击强度

数据保证:

• $1 \leq N \leq 10^{500} ，且不存在前导0$

Output

输出仅一行，表示灵能消耗值.

因为答案可能比较大，所以你只需要输出答案mod $10^9+7$

Samples

10

7

Note

$F[1]$到$F[10]$分别为$1,1,2,1,2,2,3,1,2,2.$

答案是$7$

Resources

2016 UESTC Training for Dynamic Programming