UOJ Logo LFYZ Online Judge

LFYZOJ

#363. [2019年1月清北学堂dp图论专讲班]难题

统计

问题描述

在苦修30年后,你终于如愿以偿地成为了大魔法师,成功穿越到了异世界。

你原本以为你终于可以在异世界到达人生巅峰。可天妒英才好景不长,你在一次试图装逼的表演中膜法不慎失控,导致你的身体被恐怖的献祭魔力反噬。尽管你终于被好基友救活,可是你发现你的身体一直处于一种“被续”的状态,正是这种后遗症导致你的身体变成了魔法绝缘体,你体内产生的所有魔力在第一时间就会被献祭,于是你开始为了夺回自己的膜法而努力…………………………

……………………………………………………………………………………

终于又在3年后,你打听到了在中央海域的一个小岛上,有一座蛙神社,用神社里的水沐浴身体就可以解除反噬诅咒,于是你克服了九九八十一难寻觅到了神社,却发现神社被魔法阵所封印,而魔法阵的一侧立着一块石碑。根据古老的传说,只有完成石碑上考验的人才能进入神社。

现在你到了石碑前,发现石碑是这么写的:

一种有名的加密魔法,是把一个十进制数的每个数码做一个异或和,如 $1234$ 经过加密魔法就变成了 $4$

现在石壁考验的就是你对加密魔法的理解程度,石壁每次给出两个数 $N$ 和 $M$($N$,$M$的位数不超过$10^5$),你需要在极快的时间内回答石壁 $N-M$ 所有的数的加密后的和是多少,答案会很大请对$10^9+7$取模。

输入格式

本题读入为多组测试数据!

本题读入为多组测试数据!

本题读入为多组测试数据!

一共 $T$ 组测试数据

接下来每组测试数据一共两行,每一个数字表示 $N,M$ 的值

输出格式

每组测试数据输出一行答案,答案会很大,请对$10^9+7$取模

样例一

input

3
1234
1234
1
10
9999
99999

output

4
46
649032

数据范围与约定

$1<=T<=20$

对于20%的数据,$N,M$不超过$10^5$

对于100%的数据,$N,M$的位数不超过$10^5$

时间限制: $2\mathrm{s}$

内存限制: $256\mathrm{MB}$