For a positive integer $n$, a $3^n \times 3^n$ 01-matrix $A_n$ is defined as follows: If $3^{n-1} \le i < 2 \times 3^{n-1}$ or $3^{n-1} \le j < 2 \times 3^{n-1}$, then $$A_n(i, j) = \begin{cases} 1, & n = 1 \\ A_{n-1}(i \bmod 3^{n-1}, j \bmod 3^{n-1}), & n \ge 2 \end{cases}$$ where $x \bmod y$ denotes the remainder of $x$ divided by $y$. Otherwise, $A_n(i, j) = 0$.

Here, $A_n(i, j)$ denotes the element in the $i$-th row and $j$-th column of matrix $A_n$, with both row and column indices starting from 0.

Given a positive integer $n$, Little C has two digit strings of length $n$, where each digit is one of $0, 1, 2$, representing two ternary numbers $n_1, n_2$ (which may contain leading zeros). You need to help Little C find the value of $A_n(n_1, n_2)$.

Input

The first line contains a positive integer $n$ ($1 \le n \le 10^5$). The next two lines each contain a digit string of length $n$, representing the ternary numbers $n_1$ and $n_2$, respectively.

Output

Output a single integer representing the value of $A_n(n_1, n_2)$.

Examples

Input 1

2
20
01

Output 1

0

Note 1

In fact, for $n=2$: $$A_2 = \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$ The input digit strings correspond to $n_1 = 6$ and $n_2 = 1$, thus $A_2(n_1, n_2) = 0$.

Input 2

3
102
011

Output 2

1