小慕在异国旅行时，发现该国使用。小慕有一个幸运数字n（n < m），每次购物时，小慕总喜欢计算本次支付的花费（折算成异国价格后）中出现了多少次幸运数字。请问：当小慕购买一个在我国价值为k的产品时，其中包含多少个幸运数字？
提示：带虚线的词点一下有通俗解释。
输入描述
第一行输入为k n m k 表示 该客人购买的物品价值 (以十进制计算的价格) n 表示 该客人的幸运数字 m 表示 该客人所在国度的采用的进制
输出描述
输出幸运数字的个数，行末无空格.
示例
示例 1
输入
10 2 4
输出
2
说明：10 = 2 * 4^1 + 2 * 4^0 = 22(四进制) 22一共包含2个2，故答案为2
时间限制 1000 ms · 内存限制 128 MB