Counting Realizable Independent Set Sequences

Given a nonnegative integer sequence a of length n (with 0 ≤ a_i ≤ m) we define its corresponding independent set sequence f(a) as follows:

• For each index i (1 ≤ i ≤ n), let a′ be the sequence obtained from a by setting a_i = 0. Then, considering the standard maximum weighted independent set on a line (i.e. selecting a subset of indices no two of which are consecutive such that the sum of the corresponding numbers is maximized), we define f(a)_i to be the maximum sum obtained on a′.

Formally, if for any sequence x of length L we define the DP value by:

$$\begin{aligned} dp(0)&=0,\\ dp(1)&=x_1,\\ dp(i)&=\max\{dp(i-1),\;dp(i-2)+x_i\} \quad \text{for } i\ge2, \end{aligned}$$

then f(a) is defined by

$$f(a)_i = dp_{a^{(i)}}(n) \quad\text{where } a^{(i)} \text{ is } a \text{ with } a_i=0. $$

Now, given three integers n, m and a prime MOD, count the number of nonnegative integer sequences b (of length n) for which there exists at least one sequence a (of length n with each a_i in [0, m]) satisfying

$$f(a)=b.$$

Output your answer modulo MOD.

Note: For each index the value f(a)_i is computed by independently applying the maximum weighted independent set procedure on the sequence with the i-th element replaced by 0. In many cases an optimal solution to the independent set problem may choose to omit an index; if so, f(a)_i will equal the overall optimum. Otherwise, if the index was essential, setting it to 0 will lower the optimal sum. Count the number of possible b sequences (the image of f) that are realizable from some a.

inputFormat

The input consists of a single line containing three space‐separated integers:

• n – the length of the sequence a (and b).
• m – the maximum value allowed in a (i.e. 0 ≤ a_i ≤ m).
• MOD – a prime number for taking the answer modulo MOD.

It is guaranteed that the constraints are small enough for a brute force solution.

outputFormat

Output a single integer – the number of realizable independent set sequences b modulo MOD.

sample

1 1 1000000007

1

</p>