P12607 C. Ternary Tree Traversal

The problem background is not important.

You are given an infinite ternary tree rooted at vertex $0$. The children of vertex $i$ are the vertices $3i+1$, $3i+2$, and $3i+3$. Let $a_i$ denote the value written on vertex $i$. It is guaranteed that for all $i \ge 0$ and $0 \le j \le 2$, we have $a_{3i + j + 1} = 3 \times a_i + j$. Your task is to count the number of simple paths with length equal to $d$ starting at vertex $0$ such that the sum of the values along the path equals $k$. However, $k$ is not completely specified: some digits in its ternary representation are replaced with the character $?$, indicating unknown digits. Your task is to compute the total number of such paths across all valid values of $k$, considering all ways to replace each $?$ with a digit from ${0,1,2}$.

The first line contains a single integer $d$. Next line contains the ternary representation of $k$. The ternary string may contain leading zeros and question marks, and its length is exactly $d$.

Print a single integer — the total number of valid simple paths modulo $10^9 + 7$.

### Sample Explanation #1 The legal paths are: - $[0,1,5,17]$ - $[0,2,7,23]$ - $[0,2,9,30]$ These paths correspond to the following sequences of vertex values: - $[0,0,1,4]$ - $[0,1,3,10]$ - $[0,1,5,17]$ ### Data Range |TestCase #|$d$|Special Constraints| |:----:|:----:|:----:| |$1\sim 2$|$\leq15$|-| |$3$|$\leq50$|A| |$4$|$\leq50$|B| |$5\sim 8$|$\leq50$|-| |$9\sim 10$|$\leq300$|A| |$11\sim 12$|$\leq300$|B| |$13\sim 14$|$\leq300$|-| |$15$|$\leq2000$|A| |$16$|$\leq2000$|B| |$17\sim 20$|$\leq2000$|-| A: It is guaranteed that the number of $?$s in $k$ is no more than $1$. B: $k$ only contains $?$. It is guaranteed that for all testcases, $1\le d\le 2000,0\le k\lt 3^{d+1}$.