帅气的男孩子
描述
“嗨,给你看张照片。”木姑娘今天特别开心。
“就这个男孩子,你说他帅么?”木姑娘满脸泛着绯红。
木姑娘,找到了她喜爱的男孩子。听说,是隔壁班的男孩子;听说,文化课很差;听说,他喜欢过很多女孩;听说,他也分手过很多女孩;还听说,在我独自一人身处上海的时候,木姑娘经常,和他一起散步。
那或许真的是木姑娘心中,帅气的男孩子。
木姑娘总会给很多男生一个非负整数的编号,如果编号的值是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。