Background

Dear Ling,
  Hey, do you know? I heard that sakura petals fall at a speed of five centimeters per second.
  ...So, wait a little longer! March, Wuhan University, the sakura are coming soon.
  You will watch them with me, right? Under the soft sunshine, I will quietly hold your hand and feel that familiar warmth of yours. Oh no, my face is also accidentally tinted red by the pink sakura.
  By the way, remember to bring a mask! You were still a bit weak at that time. But Tianyi will protect you.
  And also, sakura can be made into so many, so many desserts! Let’s collect some falling sakura petals. I want to drink sakura tea, and I also want to eat sakura mochi. You must make them for me with your own hands!

Problem 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