H. Scratch Expressions
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Touhemi is interested in betting, specifically in Scratch Expressions.

Touhemi buys a card that reveals, when scratched, a hidden string of length $$$n$$$, generated uniformly at random from the alphabet $$$$$$ \Sigma =\{(,),+,-,*,0,1,2,3,4,5,6,7,8,9\}. $$$$$$

The string is interpreted as an arithmetic expression under the standard rules described below.

He only has to scratch the card and hope that this is a winning card. Each generated string belongs to exactly one of the following categories:

  • Winner: the string is a valid expression and evaluates to $$$0$$$ (after applying modulo $$$m$$$).
  • Loser: the string is an invalid expression, or if it evaluates to $$$k\neq 0$$$ (after applying modulo $$$m$$$)

A string is a valid arithmetic expression if and only if:

  • It consists of digits 0-9, binary operators +, -, *, and parentheses().
  • Parentheses are balanced and properly nested.
  • All operators are binary.
  • Each digit represents a single non-negative integer.
  • The entire string forms exactly one expression.

Valid Arithmetic Expressions are defined using the following recursive rules:

  • An expression is either:
    1. A sum, difference or product of two sub-expressions
    2. A sub-expression, grouped by paranthesis
    3. A number. Note that leading zeros are allowed
  • A Number is a sequence of digits
  • A Digit is a character in $$$\{0,1,2,3,4,5,6,7,8,9\}$$$

Any string that does not satisfy these rules is considered invalid.

The valid arithmetic expression is evaluated using standard arithmetic semantics (Detailed in Notes).

Any strings of length $$$n$$$ is generated uniformly at random from the alphabet $$$\Sigma =\{(,),+,-,*,0,1,2,3,4,5,6,7,8,9\}.$$$

Your task is to compute, for each given length $$$n$$$, the probability that Touhemi obtains a Winner card.

Input
  • The first line contains two integers $$$1\le T \le 10^2$$$ and $$$1\le m \le 10^2$$$ with
    • $$$1 \le T \le 100$$$: The number of test cases
    • $$$1\le m \le 100$$$: The modulus shared for all test cases
  • The second line contains $$$T$$$ integers $$$1 \le n_1, \dots,n_T \le 200,$$$ denoting the length of the expressions.
Output

It can be proven that each probability can be expressed as a ratio $$$\frac{p}{q}$$$ where $$$q \not\equiv 0 \pmod M$$$, with $$$M=10^9+7$$$.

You have to express the probability as: $$$$$$ p \times q^{-1} \bmod M, $$$$$$ where $$$q^{-1}$$$ is the modular inverse of $$$q$$$ modulo $$$M$$$.

Examples
Input
5 5
1 2 3 7 10
Output
933333340
288888891
887703710
700873106
13278558
Input
3 67
52 36 7
Output
987476354
514150140
799551473
Note

Valid Arithmetic Expressions

Formally, the set of all valid arithmetic expressions can be described by the grammar: $$$\mathcal{G} = (\{E, N, D\},\ \Sigma,\ \mathcal{R},\ E)$$$

where:

  • $$$E$$$ (expression), $$$N$$$ (number), and $$$D$$$ (digit) are the symbols.
  • $$$\Sigma = \{(, ), +, -, *, 0,1,2,3,4,5,6,7,8,9\}$$$ is the set of characters.
  • $$$E$$$ is the start symbol.
  • $$$\mathcal{R}$$$ contains the production rules, described in the table below:
|p{5.5cm}|p{8cm}|

Rule

DefinitionExplanation
Sum$$$E\rightarrow E+E$$$An Expression can be formed by adding two sub-expressions.
Difference$$$E\rightarrow E-E$$$An Expression can be formed by subtracting one sub-expression from another.
Product$$$E\rightarrow E*E$$$An Expression can be formed by multiplying two sub-expressions.
Parenthesis$$$E\rightarrow (E)$$$An Expression can be surrounded by parentheses to form a new expression
Number is Expression$$$E\rightarrow N$$$An Expression can be a single number
Append Digits$$$N\rightarrow NN$$$A Number can be formed by concatenating two shorter numbers.
Digit is Number$$$N\rightarrow D$$$A Number can be a single Digit
Digit$$$D \rightarrow 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9$$$A digit is a character from the set $$$\{0,1,2,3,4,5,6,7,8,9\}$$$
}

Generating Valid Arithmetic Expressions

Starting from $$$E$$$, we repeatedly apply the production rules to replace symbols with other symbols or characters until only characters from $$$\Sigma$$$ remain, forming a valid arithmetic expression.

For example, to generate $$$(02+35)*4$$$: $$$$$$ E \Rightarrow E*E\Rightarrow (E)*N \Rightarrow (N+N)*N \Rightarrow (NN+NN)*D \Rightarrow (DD+DD)*D \Rightarrow (02+35)*4 $$$$$$

It can be proven that any valid arithmetic expression can be generated from the start symbol $$$E$$$ by a finite sequence of production rules.

Standard Arithmetic Semantics

The standard arithmetic semantics (i.e evaluation order) are:

  • Operator precedence: * has higher precedence than + and -. E.g., 2 + 3 * 4 equals 14
  • All operators are left-associative. E.g., 10 - 3 - 2 equals 5
  • Parentheses override precedence. E.g., (2 + 3) * 4 equals 20
  • All computations are performed modulo $$$m$$$.