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 \lt b$$$ or $$$b \lt 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$$$.