Với hai số nguyên dương ~n~ và ~k~. Đặt:

$$ S = 1 \times 2 \times \ldots \times k + 2 \times 3 \times \ldots \times k \times (k+1) + \cdots + (n-k+1) \times (n-k+2) \times \ldots \times n $$

Ví dụ: ~n = 7, k = 2~ ta có: ~S = 1 \times 2 + 2 \times 3 + 3 \times 4 + 4 \times 5 + 5 \times 6 + 6 \times 7 = 112~

Yêu cầu: Cho hai số nguyên dương ~n~ và ~k~. Hãy tính ~S~.

Dữ liệu

Vào từ tệp văn bản SUMSEQ.INP ba số nguyên ~n, k, m~ (~1 \le m, n \le 10^{18}~; ~k \le n~; ~1 \le k \le 1000~).

Kết quả

Ghi ra tệp văn bản SUMSEQ.OUT phần dư của ~S~ khi chia cho ~m~.

Ví dụ

SUMSEQ.INP

7 2 10

SUMSEQ.OUT

2

Giới hạn

• Có 20% số test tương ứng với 20% số điểm của bài với ~k \le 10~; ~m, n \le 10^9~.
• Có 80% số test tương ứng với 80% số điểm của bài với ~10^9 < m, n \le 10^{18}~.