P17266 [ICPC 2017 Urumqi R] Count Numbers

现在 Alice 想要对所有数位和恰好为 $a^b$ 的整数求和。 然而我们知道，这类整数的数量是无限的。因此她决定改为对所有满足下述条件的数求和：每个数位均非零。 由于答案可能很大，她只需要答案模给定整数 $p$ 的余数。

输入包含多组测试数据，第一行是一个整数 $t$ ($1 \le t \le 400$)，表示测试数据的组数。 对于每组测试数据，一行包含三个整数 $a, b$ ($1 \le a, b \le 20$) 和 $p$ ($2 \le p \le 10^9$)，分别描述了数位和的限制以及给定的模数 $p$。

对于每组测试数据，输出一行包含所需的答案。 这里我们为下面的样例输出提供一个解释。在输入中，满足限制的所有整数为 $4, 13, 31, 22, 121, 112, 211$ 和 $1111$。它们的总和为 $4 + 13 + 31 + 22 + 121 + 112 + 211 + 1111 = 1625$，这恰好是样例输出之一。

翻译由 DeepSeek V4 Pro 完成