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:
A string is a valid arithmetic expression if and only if:
Valid Arithmetic Expressions are defined using the following recursive rules:
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.
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$$$.
5 5 1 2 3 7 10
933333340 288888891 887703710 700873106 13278558
3 67 52 36 7
987476354 514150140 799551473
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:
| |p{5.5cm}|p{8cm}| Rule | Definition | Explanation |
| 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: