奇偶差值数

题目描述

所谓 k-奇偶差值数，指一个正整数，满足所有偶数位上数字之和减所有奇数位上数字之和的差值为给定数字 $k$。（我们认为个位为第1位，十位为第2位，以此类推…）

现给定三个正整数 $l, r, k$，请你求出在区间 $[l, r]$ 范围内有多少个 k-奇偶差值数。

例如，当 $l=100，r=1000，k=6$ 时，共有 6 个 6-奇偶差值数，分别是：$170, 181, 280, 192, 291, 390$。

输入格式

• 输入共一行，三个正整数分别表示 $l, r, k$。

输出格式

• 输出共一行，表示满足条件的 k-奇偶差值数个数。

数据范围

• 对于 $50\%$ 的数据，$1 \leq l \leq r \leq 10^6$
• 对于 $100\%$ 的数据，$1 \leq l \leq r \leq 10^{13}$，$1 \leq k \leq 70$

样例数据

输入:

100 1000 6

输出:

6

输入:

1 10 5

输出:

0

在这个例子中，我们需要找到区间内所有数字的奇数位和偶数位上的数字和的差值恰好为 $k$ 的情况数。