#3588. fx

内存限制:256 MiB 时间限制:20 Sec

题目描述

  对于一个n位的十进制数x(AnAn-1……A1),我们定义它的权重为:
  F(x)=An*2n-1+An-1*2n-2+……+A1*20
  现在,给你两个十进制数A和B,请计算出在闭区间[0, B]之中,有多少个数x的权重不大于A的权重,即F(x)<=F(A)。由于答案可能很大,你只需要输出答案对1000000007(109 + 7)取模的结果即可。

输入格式

  第一行一个正整数T,表示测例的个数。
  随后T行,每行描述一个测例,包含两个非负整数A、B,之间用空格隔开。含义见问题描述。

输出格式

  对于每个测例,单独输出一行”Case #t: ans”,其中t表示测例编号,从1开始递增,ans表示该组测例的答案(对1000000007取模后的结果)。

样例

样例输入


			
3
0 100
1 10
5 100

样例输出


			
Case #1: 1
Case #2: 2
Case #3: 13

数据范围与提示

样例说明

  对于Case #3,符合条件的数有0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 20, 21, 100,共13个。


  //样例描述有修改,请注意!

数据规模及约定

  对于20%的数据,A, B <= 10^9;

  对于30%的数据,A, B <= 10^18;


  对于100%的数据,A,B <= 10200,T<=5。