Give you three integers n, A and B.
Then we define S
i = A
i mod B and T
i = Min{ S
k | i-A <= k <= i, k >= 1}
Your task is to calculate the product of T
i (1 <= i <= n) mod B.
Each line will contain three integers n(1 <= n <= 10
7),A and B(1 <= A, B <= 2
31-1).
Process to end of file.
For each case, output the answer in a single line.