Cho \(n\) số nguyên liên tiếp từ 1 đến \(n\) và hai số nguyên dương \(k, m\).
Với mỗi \(i\), ta định nghĩa giá trị \(C_i\) là tích \(k\) số liên tiếp từ \(i-k+1\) đến \(i\): \(C_i = (i - k + 1) × (i - k + 2) × … × (i - 1) × i\).

Ví dụ: \(n = 6,k = 3\), ta có các giá trị: \(C_3=1×2×3, \ C_4=2×3×4, \ C_5=3×4×5, \ C_6= 4×5×6\).

Yêu cầu: Cho \(n,k,m\), hãy tính tổng \(S=C_k+C_{k+1}+⋯+C_n\). Vì \(S\) có thể rất lớn nên bạn chỉ cần in ra phần dư của \(S\) cho \(m\)
.

Input

• Một dòng ghi 3 số \(n,k,m \ (n \leq 10^{18},k \leq 500,m \leq 10^{18})\).

Output

• Một số duy nhất là giá trị của \(S\).

Example

6 3 1234 

210

10 5 666013 

55440