题目描述

交通部正在准备一次车票编号改革。负责方案审核的伊戈尔决定采用一种新的编号规则：每张车票由 $q$ 位 $n$ 进制数字组成，其中 $q$ 是质数。编号允许有前导零。

设一张车票的数字为

$$a_1a_2\ldots a_q.$$

如果所有数字的乘积加上所有数字的和，再对 $n$ 取模后等于 $s$，即

$$\left(\prod_{i=1}^q a_i+\sum_{i=1}^q a_i\right)\bmod n=s,$$

那么这张车票被称为幸运车票。

每张幸运车票还有一个幸运度。数字为 $a_1a_2\ldots a_q$ 的车票，其幸运度定义为

$$(a_1+1)(a_2+2)\cdots(a_q+q)+2^0a_1+2^1a_2+\cdots+2^{q-1}a_q.$$

现在需要在改革报告中计算所有幸运车票的幸运度之和，并对 $q$ 取模。请输出这个值。

输入格式

第一行包含三个整数 $n,s,q$。

输出格式

输出一行一个整数，表示所有幸运车票的幸运度之和对 $q$ 取模后的结果。

数据范围

• $2\le n\le 10^6$；
• $0\le s<n$；
• $2\le q\le 10^6$；
• $q$ 是质数。

样例 1

输入

2 0 2

输出

0

样例 2

输入

10 9 2

输出

1

样例 3

输入

3 2 3

输出

2