U687409 阶乘消去p再模p的a次方

定义 $(n!)_p$ 除去所有的因数 $p$ 之后剩余的整数。 比如： $$(6!) = 6 \times 5 \times 4 \times 3 \times 2 \times 1$$ $$= 720$$ $$(6!)_3 = 2 \times 5 \times 4 \times 1 \times 2 \times 1$$ $$= 80$$ $$(6!)_2 = 3 \times 5 \times 1 \times 3 \times 1 \times 1$$ $$= 45$$ 现在给你三个整数 $n, p, a$，求 $$(n!)_p \pmod {p^a}$$

一行，三个整数 $n, p, a$，以空格分隔。

输出一个整数，表示 $(n!)_p \pmod {p^a}$ 的值。

#### 数据规模与约定 - 对于 $100\%$ 的数据，$1 \le n \le 10^{12}$，$p$ 是素数，$a$ 是一个正整数，且 $p^a \le 10^7$