百度之星2009初赛第二轮题四------公平数

问题背景

如果一个整数的十六进制表示（不含前导0）中，前一半数字之和等于后一半数字之和，我们称它为公平数。
注意，如果该数的十六进制表示中包含奇数个数字，则正中间的数字既不属于前一半，又不属于后一半。

例如在十六进制下1+D=7+7，因此1DE77是公平数。数字E并不参与计算。
再例如，所有单个数字的十六进制数（即0~F）均为公平数，但F0不是（不能把F0补充前导0写成0F0，进而认为它是公平数）。

给出十六进制数 X, Y, K 和十六进制数字集合 S，求区间[X, Y]之内，有多少个公平数满足：

• 十六进制表达式（不包含前导0）中每个数字均在集合S中
• 并且为K的倍数

输入格式

输入第一行为数字集S，包含0~9以及大写字母A~F。
每个数字或字母最多出现一次。
第二行包含 3 个十六进制正整数K, X, Y，均不超过 10 个数字。

输出格式

仅一行，包含一个整数，即满足条件的公平数个数。

样例输入

124C
5 100 FFF

样例输出

4

样例解释

只有四个数满足条件：212，424，4C4，C1C。