Description

Sentences related to the task have been bolded.

But don’t rush. Let’s just keep walking slowly like this. No need to stop or look back. Aren’t there still $k$ sakura trees ahead? I calculated it: you need to collect exactly $n$ sakura petals. I also found that under the $i$-th tree, you can collect at most $s_i$ sakura petals (collecting $0$ sakura petals also counts as collecting sakura petals).

Now, let me test you. How many different plans are there to collect exactly $n$ sakura petals?

In particular, if you cannot collect $n$ sakura petals, please tell me impossible.

Note: If you reach $n$ sakura petals early, you may tell me immediately, or you may keep walking with me. But after collecting sakura petals under the $k$-th tree, you must report your result. During the process, if you tell me after collecting sakura petals under any tree, the resulting plans are considered different.

Input Format

The first line contains two positive integers $n, k$, meaning you need to collect $n$ sakura petals, and there are $k$ sakura trees ahead.

The next line contains $k$ positive integers $s_1, s_2, \cdots, s_k$, where $s_i$ means you can collect at most $s_i$ sakura petals under the $i$-th sakura tree.

Output Format

Output one integer per line, representing the number of plans to collect exactly $n$ sakura petals.

Since the answer may be very large, output the result modulo $10086001$.

In particular, if it is impossible to collect $n$ sakura petals, output the string impossible.

3 4
1 1 1 1

5

10 9
9 6 8 7 9 6 5 4 3

68345

10 5
2 2 2 2 1

impossible

Hint

Sample Explanation #1

We use the following way to represent a plan: $(a_1, a_2, \cdots, a_{len})$, where $\sum_{i=1}^{len} a_i = n$, $len$ means you report after finishing collecting sakura petals under the $len$-th tree, and $a_i$ means you collected $a_i$ sakura petals under the $i$-th tree.

Then there are $5$ plans: $(1,1,1)$, $(1,1,1,0)$, $(0,1,1,1)$, $(1,0,1,1)$, $(1,1,0,1)$.

Sample Explanation #3

You can collect at most $9$ sakura petals, so you cannot collect $10$ sakura petals, and the output is impossible.

Constraints

This problem uses bundled tests.

• Subtask 1 (5 Points), $\sum s_i < n$.
• Subtask 2 (20 Points), $n, k \leq 20$.
• Subtask 3 (55 Points), $n, k \leq 5 \times 10^2$.
• Subtask 4 (20 Points), $n, k \leq 5 \times 10^3$.

For $100\%$ of the testdata, $1 \leq n, k \leq 5 \times 10^3$, $0 \leq s_i \leq n$.

Background (Continued)

  Someone as smart as you will surely stand under some tree, holding $n$ lovely sakura petals, and ask for credit from me like a child.
  Then don’t blame me for granting your wish. I will lightly jump up, wrap my arms around your neck, lift your mask, and taste your lips.
  Will you say, “Sweet like sakura”?
  Anyway, my face must already be as red as sakura.
  ...
  When you read this letter, don’t cry...
  What winter took away from this city, spring will make up for us.
  When you get better, go watch sakura with me, okay?

Yours,
Yi

Translated by ChatGPT 5