Cho số nguyên dương n và hai số nguyên dương a, m. Hãy xác định dãy w₁, w₂, …, w_n theo công thức:

w_i = (aⁱ mod m) + 1

Nhiệm vụ

Tính tổng của dãy số này.

Input

Ba số nguyên n, a, m (1 ≤ n, a, m ≤ 10⁵).

Output

Tổng của dãy số.

Ví dụ

Input

5 4 9

Output

28

Giải thích: dãy thu được là 5, 8, 2, 5, 8.