P17266 [ICPC 2017 Urumqi R] Count Numbers

Now Alice wants to sum up all integers whose digit sum is exactly $a^b$. However we all know the number of this kind of integers are unlimited. So she decides to sum up all these numbers whose each digit is non-zero. Since the answer could be large, she only needs the remainder when the answer divided by a given integer $p$.

The input has several test cases and the first line contains the integer $t (1 \le t \le 400)$ which is the number of test cases. For each test case, a line consisting of three integers $a, b (1 \le a, b \le 20)$ and $p (2 \le p \le 10^9)$ describes the restriction of the digit sum and the given integer $p$.

For each test case, output a line with the required answer. Here we provide an explanation of the following sample output. All integers satisfying the restriction in the input are $4, 13, 31, 22, 121, 112, 211$ and $1111$. The sum of them all is $4 + 13 + 31 + 22 + 121 + 112 + 211 + 1111 = 1625$ and that is exactly the sample output.