405440: GYM101962 L Code Name Hummingbird

The SIA (Soteropolis Intelligence Agency) has just engaged in a new operation code-named Hummingbird. It is responsible for the investigation of illegal biological activities in greater Soteropolis area. Tico is the one responsible for building a team for the operation. $$$n$$$ agents will be designated to it, but first they must be given code names and then be arranged hierarchically.

More specifically, Tico will arrange those $$$n$$$ agents in a line and number them from 1 to $$$n$$$, left to right. Right after that he will pick a code name for each one of the agents. The agent $$$i$$$ will receive a non-empty code name with at most $$$a_i$$$ characters. A code name is a string composed of:

• Zero or more digits from 0 to 9;
• At least one character from a set $$$S$$$ of special characters (this set doesn't contain digits from 0 to 9). The characters of this set form a total order. Therefore, given two distinct special characters $$$a, b$$$, we can say that $$$a < b$$$ or $$$b < a$$$.

Tico says that the strong character of a code name is the special character which is greater than all the others. For example, if we take $$$S$$$ as the set of English characters, the strong character of 4ak2k is k.

After that, Tico will choose a direct supervisor for each of the agents in such a way that the following properties are met:

• Each agent should have as a supervisor another agent, except for one of them, which will be the leader of the operation;
• Every agent should directly supervise at most two other agents;
• An agent can't (directly or indirectly) supervise himself. Therefore, the supervising relation forms a rooted binary tree;
• For each agent $$$i$$$, let $$$s_1, s_2, \dots, s_k$$$ be the ordered sequence of agents directly or indirectly supervised by him. If $$$s$$$ is non-empty, then $$$max(s_k, i) - min(s_1, i)$$$ should be equal to $$$k$$$. In other words, every sub-tree of this tree must be formed by agents from a contiguous subsequence of $$$1, 2, \dots, n$$$;
• The strong character of an agent's code name should be no smaller than the strong characters of the code names of the agents he supervise.

Tico defines a team as a pair of sequences $$$(g, p)$$$ such all the properties above are met, where $$$g_i$$$ is the code name of the $$$i$$$-th agent and $$$p_i$$$ is the supervisor of the $$$i$$$-th agent (or 0 if he is the team leader).

Tico is interested in counting how many distinct teams he can get by picking code names and supervisors for the agents. More specifically, he wants to count that for many different sets $$$S$$$.

Two teams $$$(g, p), (t, s)$$$ are considered different iff there is an agent $$$i$$$ such that $$$g_i \neq t_i$$$ or $$$p_i \neq s_i$$$.

The first line contains two integers $$$n, Q$$$ ($$$1 \leq n \leq 50$$$; $$$1 \leq Q \leq 50000$$$) – the number of agents and the number of sets $$$S$$$ to be considered.

The second line contains $$$n$$$ integers. The $$$i$$$-th of them is $$$a_i$$$ ($$$1 \leq a_i \leq 5$$$) – the maximum length of the code name of the $$$i$$$-th agent.

Then $$$Q$$$ lines follow. The $$$i$$$-th of them contains the size $$$|S_i|$$$ of a set of special characters ($$$1 \leq |S_i| \leq 10^9$$$).

Print $$$Q$$$ lines with a single integer in each one of them. The $$$i$$$-th of those should contain how many distinct teams can be formed considering $$$S_i$$$ as the set of special characters.

Since those numbers can be huge, you should print the module $$$10^9+7$$$.

1 2
1
1
2

1
2

1 3
2
1
2
3

22
46
72

3 2
2 3 1
5
10

2540038
28724476

In the first case, the only possible code names for $$$|S|$$$ = 2 are a and b.

In the second case, for $$$|S| = 1$$$ we have the following strings in regex notation:

1. a
2. a[0-9]
3. [0-9]a
4. aa

Summing up to 22 possible code names.