题目背景

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

题目描述

对于正整数 $n$，用如下方法定义一个 $3^n\times 3^n$ 的 $01$ 矩阵 $A_n$：

• 若 $3^{n-1}\leq i<2\times3^{n-1}$ 或者 $3^{n-1}\leq j<2\times3^{n-1}$，则 $$A_n(i,j)=\begin{cases}1, & n = 1, \A_{n-1}(i\bmod 3^{n-1},j\bmod 3^{n-1}), & n\geq 2.\end{cases}$$ 其中 $x\bmod y$ 表示 $x$ 对 $y$ 取模后的结果；

• 否则，$A_n(i,j)=0$。

其中，$A_n(i,j)$ 表示矩阵 $A_n$ 第 $i$ 行第 $j$ 列的元素，并且行、列的编号均从 $0$ 开始。

现在，给定正整数 $n$，小 C 有两个长度为 $n$ 的数字串，其中每位都是 $0,1,2$ 中的一个，代表了两个三进制数 $n_1,n_2$（可能包含前导 $0$）。你需要帮小 C 求出 $A_n(n_1,n_2)$ 的值。

输入格式

第一行输入一个正整数 $n (1\leq n\leq 10^5)$，含义见题目描述。

接下来两行，每行输入一个长度为 $n$ 的数字串，分别表示三进制数 $n_1,n_2$。

输出格式

输出一个整数，表示 $A_n(n_1,n_2)$ 的值。

2
20
01

0

3
102
011

1

提示

事实上，$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} $$

而输入的数字串分别对应 $n_1=6,n_2=1$，进而 $A_2(n_1,n_2)=0$。