题目描述

给定两个十进制表示的整数 $a$ 与 $b$，再给定一个 $b$ 进制的整数 $c$，请求出从 $1$ 到 $c$ 的所有是 $a$ 的倍数的整数，在 $b$ 进制下的数位的和。

由于答案可能很大，输出这个和除以 $1,000,000,007$ 的余数。

输入格式

• 第一行：两个十进制整数 $a$ 与 $b$
• 第二行：一个 $b$ 进制整数 $c$

输出格式

• 单个整数，表示数位之和除以 $1,000,000,007$ 的余数，以十进制输出。

3 10
16

27

样例解释 1

3+6+9+1+2+1+5

数据范围

记 $|c|$ 表示 $c$ 的长度

• $30\%$ 的数据，$b=10$，$1\leq |c| \leq 5$
• 对另外 $30\%$ 的数据，$b=2$，$1\leq |c| \leq 500$
• $100\%$ 的数据，$b\leq 10$，$1\leq |c| \leq 10,000$
• $1\leq a\leq 100$