政府计划进行一项交通改革，这将改变车票号码。新的车票号码将由 $n$ 进制下的 $q$ 位数字组成，其中 $q$ 是一个质数。允许前导零。

如果一张车票所有数字的乘积加上所有数字的和，对 $n$ 取模的结果等于 $s$，则称该车票是幸运的。此外，每张幸运车票都有一个幸运度：对于数字为 $a_1 a_2 \dots a_q$ 的车票，其幸运度等于 $$(a_1 + 1)(a_2 + 2) \dots (a_q + q) + 2^0 a_1 + 2^1 a_2 + \dots + 2^{q-1} a_q$$

为了完成改革报告，需要计算所有幸运车票的幸运度之和，结果对 $q$ 取模。

输入格式

第一行包含三个整数 $n, s$ 和 $q$ ($2 \le n \le 10^6, 0 \le s < n, 2 \le q \le 10^6, q$ 为质数)。

输出格式

输出所有幸运车票的幸运度之和，结果对 $q$ 取模。

样例

样例输入 1

2 0 2

样例输出 1

0

样例输入 2

10 9 2

样例输出 2

1

样例输入 3

3 2 3

样例输出 3

2