Xét phương trình \(𝑥_1 + 𝑥_2 + ⋯ + 𝑥_𝑘 = 𝑛\), trong đó \(𝑥_1, 𝑥_2, … , 𝑥_𝑘\) là các biến nguyên dương thỏa
mãn ràng buộc: \(𝑥_𝑖 ≥ 𝑐_𝑖 > 0\).

Ví dụ:

\(\left\{\begin{matrix} x_1+x_2+x_3=7\\ x_1\geq 1\\ x_2\geq 2\\ x_3\geq 3 \end{matrix}\right.\)

Phương trình có ba nghiệm sau: \((1;2;4); (1;3;3); (2;2;3)\).

Yêu cầu: Cho \(𝑛, 𝑘, 𝑐_1, 𝑐_2, … , 𝑐_𝑘\), hãy đếm số nghiệm của phương trình.

Input

• Dòng đầu chứa 3 số nguyên dương \(𝑛, 𝑘, 𝑀\ (𝑀 \le 10^9)\);
• Dòng thứ hai gồm \(𝑘\) số nguyên dương \(𝑐_1, 𝑐_2, … , 𝑐_𝑘 (𝑐_𝑖 \le 𝑛)\).

Output

• Gồm một dòng là số nghiệm của phương trình chia dư cho \(𝑀\).

Scoring

• Subtask \(1\): \(𝑘 \le 𝑛 \le 20\);
• Subtask \(2\): \(𝑘 \le 𝑛 \le 2000\);
• Subtask \(3\): \(𝑘 \le 𝑛 \le 2000000\);

Example

7 3 100
1 2 3

3