Problem 990
Addition Equations
A string forms an addition equation if it consists of
- Digits, forming positive integers. No leading zeros are allowed.
- A single plus sign between integers.
- A single equality sign.
Most importantly, the equality must hold.
Example of strings of length $7$ forming addition equations:
1+1+1=3
100=100
77=7+70
1+2=2+1
Note that strings are considered different even if they form equivalent equations, so for example here are three unique strings:
1+2=3
2+1=3
3=1+2
The following strings do not form valid addition equations:
1+1=3
1+1=02
0+1=1
+1=1
2-1=1
Let $A(n)$ be the number of strings of length not larger than $n$ forming addition equations.
You are given $A(3) = 9$, $A(5)=171$ and $A(7)=4878$.
Find $A(50)$. Give your answer modulo $10^9 + 7$.
加法等式
如果一个字符串仅包含
- 由数字组成、没有前导零的正整数；
- 一个加号，位于正整数之间；
- 一个等号；
且最重要的是，等式必须成立，则称其构成了一个加法等式。
如下是长度为$7$且构成加法等式的字符串示例：
1+1+1=3
100=100
77=7+70
1+2=2+1
注意，即使字符串构成的不同等式是等价的，它们仍被视为不同的字符串，因此如下是三个不同的字符串：
1+2=3
2+1=3
3=1+2
而如下字符串不构成合法的加法等式：
1+1=3
1+1=02
0+1=1
+1=1
2-1=1
记$A(n)$为长度不超过$n$且构成加法等式的字符串数目。
已知$A(3) = 9$，$A(5)=171$，$A(7)=4878$。
求$A(50)$，并对$10^9 + 7$取余作为你的答案。