Description

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}$.

Input Format

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$.

Output Format

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

3
?12

3

3
???

19

4
0211

1

10
21??1?2??0

161

30
???1????0????1???0????2???????

744432249

Hint

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

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}$.