"Some people are shallow, some are smooth on the outside but rotten on the inside. One day, you will meet someone who is as colorful as a rainbow, and when you do, you will realize that everyone else is just a passing cloud." —— Flipped

Y felt a deep resonance after watching this movie. In Y's eyes, y is that person as colorful as a rainbow. However, Y is unsure of y's feelings and lacks confidence in himself. Y often comforts himself by saying that the time is not yet right, that he must wait and be patient.

Thoughts by day, dreams by night. One day, Y meets y in a dream. He stands foolishly in front of y, wanting to say something but unable to speak. Suddenly, a voice comes from the sky, "This is just a dream," and the y before him dissipates like smoke. A long-bearded elder with wings on his back slowly approaches from the distance.

This person claims to be Cupid, the god of love. Y believes this deeply, even exclaiming, "I have never been superstitious, I only believe in the god of love."

Cupid tells Y, "I can help you confess to y, but there is one condition." Cupid then writes down two functions: $$ f(i)=(k*i)^{k*i*[i \text{ is prime}]}\\ (f(i)=(k*i)^{k*i} \text{ if } i \text{ is prime, otherwise } f(i)=1)\\ g(i)=(k*i)^{k*\varphi(i)}\\ (\varphi(i) \text{ denotes the number of integers less than or equal to } i \text{ that are coprime to } i) $$

Then he writes down four expressions:

$$ 1.\prod\limits_{i=1}^n f(i)\\ 2.\prod\limits_{i=1}^n g(i)\\ 3.\prod_{i=1}^n\prod_{j=1}^{\lfloor \frac{n}{i}\rfloor}f(j)^{\lfloor\frac{n}{j}\rfloor}\\ 4.\prod_{i=1}^n\prod_{j=1}^{\lfloor \frac{n}{i}\rfloor}g(j)^{\lfloor\frac{n}{j}\rfloor}\\ $$

Cupid provides the values of $n$ and $k$, and asks Y to answer the values of the first $m$ expressions, with the answers taken modulo $1\,000\,000\,007$.

Input

A single line containing 3 positive integers $n, k, m$, as described in the problem.

Output

Output $m$ lines, each containing an integer. The integer on the $i$-th line represents the answer to the expression numbered $i$.

Examples

Input 1

233 233 4

Output 1

591645143
124162718
818917434
181711594

Input 2

166666667 1 2

Output 2

734298437
771861883

Constraints