Coin Change Ways - Classic Problems | Repovive

CLS63. Coin Change Ways

2s256 MB

Given coin values, a target, and a modulus $m$ , count the number of unordered ways to form the target. Each coin value may be used any number of times.

Constraints

$1 \le n \le 100$
$0 \le target \le 2 \cdot 10^5$
$1 \le c_i \le 2 \cdot 10^5$
$2 \le m \le 10^9 + 7$

Input

\begin{array}{l} n \quad target \quad m \\ c_1 \quad c_2 \quad \ldots \quad c_n \end{array}

Output

ways \bmod m

Samples

Input

3 5 1000000007
1 2 5

Explanation

The unordered ways are 5, 2+2+1, 2+1+1+1, and five 1s, so the answer is 4.

Output

Input

2 3 17
2 4

Explanation

No combination forms target 3, so the answer is 0.

Output

Input

4 0 97
2 3 5 7

Explanation

There is exactly one way to form target 0: choose no coins.

Output

Given coin values, a target, and a modulus $m$ , count the number of unordered ways to form the target. Each coin value may be used any number of times.

$1 \le n \le 100$
$0 \le target \le 2 \cdot 10^5$
$1 \le c_i \le 2 \cdot 10^5$
$2 \le m \le 10^9 + 7$

\begin{array}{l} n \quad target \quad m \\ c_1 \quad c_2 \quad \ldots \quad c_n \end{array}

ways \bmod m