/ Vijos / 题库 /

帅气的男孩子

帅气的男孩子

描述

“嗨,给你看张照片。”木姑娘今天特别开心。

“就这个男孩子,你说他帅么?”木姑娘满脸泛着绯红。

木姑娘,找到了她喜爱的男孩子。听说,是隔壁班的男孩子;听说,文化课很差;听说,他喜欢过很多女孩;听说,他也分手过很多女孩;还听说,在我独自一人身处上海的时候,木姑娘经常,和他一起散步。

那或许真的是木姑娘心中,帅气的男孩子。

木姑娘总会给很多男生一个非负整数的编号,如果编号的值是x,那么就可以利用x从高位到地位的交错和f(x)来得到木姑娘心中的好感度。

比如说f(3214567)=3-2+1-4+5-6+7=4就是编号为3214567的男生在木姑娘心中的好感度。

好感度恰好为k的男生,就是木姑娘喜欢的“帅气的男孩子”。

那么,对于编号从l到r的所有男孩子来说,里面木姑娘喜欢的“帅气的男孩子”们的编号和是多少呢?

格式

输入格式

输入数据仅一行包含三个整数,l,r,k(0<=l<=r<=10^18,|k|<=100)。

输出格式

输出一行一个整数表示结果,考虑到答案可能很大,输出结果模 10^9+7。

样例1

样例输入1

100 121 0

样例输出1

231

样例2

样例输入2

4344 3214567 3

样例输出2

611668829

样例3

样例输入3

100 121 -1

样例输出3

120

限制

对于40%的数据,l<=r<=1000。
对于100%的数据,l<=r<=10^18。

提示

对于样例 1,满足条件的数有 110 和 121,所以结果是 231 = 110 + 121。

信息

ID
1933
难度
8
分类
a 点击显示
标签
(无)
递交数
40
已通过
6
通过率
15%
被复制
2
上传者

相关