测试数据来自 system/1933

描述

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

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

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

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

木姑娘总会给很多男生一个非负整数的编号，如果编号的值是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。