交替平衡数

题目描述

对于一个正整数 $x$，从右往左依次给每一位编号为 $1,2,3,\ldots$。

例如，数字 $58324$ 从右往左各位分别是：

• 第 $1$ 位：$4$
• 第 $2$ 位：$2$
• 第 $3$ 位：$3$
• 第 $4$ 位：$8$
• 第 $5$ 位：$5$

定义：

• 奇数位置数位和：第 $1,3,5,\ldots$ 位上的数字之和；
• 偶数位置数位和：第 $2,4,6,\ldots$ 位上的数字之和。

如果一个正整数同时满足下面两个条件，就称它为 交替平衡数：

1. 奇数位置数位和等于偶数位置数位和；
2. 它的所有数位中，恰好有 $k$ 个奇数数字（$1,3,5,7,9$）。

现在给定正整数 $L,R,k$，请你求出区间 $[L,R]$ 中有多少个交替平衡数。

输入格式

共三行：

第一行一个正整数 $L$。

第二行一个正整数 $R$。

第三行一个非负整数 $k$。

保证 $L\le R$。

输出格式

输出一行一个整数，表示区间 $[L,R]$ 中交替平衡数的个数。

样例

输入

10
99
2

输出

5

样例说明

在 $10$ 到 $99$ 中，满足条件的数为：

11 33 55 77 99

共 $5$ 个。

数据范围

对于所有测试点：

• $1\le L\le R\le 10^6$
• $0\le k\le 7$

时间限制：$1\text{s}$
内存限制：$256\text{MiB}$