TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6587
  • 题目
  • P6587异或值与和
    限制 : 时间限制 : 2000 MS   空间限制 : 1048576 KB
    问题描述

    给你一个以2为基数的正整数$L$,请你找出有多少对非负整数$(a,b)$满足下面两个条件:

    1. \(a+b \leq L\)

    2. \(a+b = a\)   XOR   \(b\)

      (XOR指的是位运算异或的意思,就是两个数对应二进制位上的数相同,则结果就为0,反之,结果为1。举个例子:2个整数$A=011$和$B=101$,\(A\)   XOR \(B=011\)   XOR   $101=110$,计算如下 :从左往右数第1个二进制位上的数不一样,所以结果第1位是1;从左往右数第2个二进制位上的数不一样,所以结果第2位也是1;从左往右数第3个二进制位上的数相同,所以结果第3位是0,结果就是110。)

    由于满足上述两个条件的非负整数对比较多,所以把这个结果对$7+10^9$取模再输出。

    其中,$L$是一个以2为基数的数,没有前缀0存在。$1 \leq L < 2^{100001}$(以2为基数可以理解为二进制数)

    输入格式

    输入$L$

    输出格式

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

    样例输入 1

    10

    样例输出 1

    5

    样例输入 2

    1111111111111111111

    样例输出 2

    162261460

    提示

    样例说明: 5对数分别是:(0,0)(0,1)(1,0)(0,2)(2,0)