超立方体图具有迷人的规律性，因此你投入了大量时间研究与之相关的数学问题。$n$ 维超立方体图的顶点是所有长度为 $n$ 的二进制字符串，如果两个顶点仅在一位上不同，则它们是相连的。超立方体图与纠错码之间存在许多有趣的联系。

其中一种联系涉及 $n$ 位格雷码（Gray Code），它是一种长度为 $n$ 的二进制字符串的排序，定义如下：$n$ 位格雷码的序列首先由 $(n-1)$ 位格雷码的单词组成，每个单词前加一个 $0$，随后是相同的单词以相反的顺序排列，每个单词前加一个 $1$。$1$ 位格雷码仅由 $0$ 和 $1$ 组成。例如，$3$ 位格雷码的序列如下：

$000, 001, 011, 010, 110, 111, 101, 100$

现在，$n$ 位格雷码构成了 $n$ 维超立方体中的一条哈密顿路径，即一条恰好访问每个顶点一次的路径（见图 H.1）。

图 H.1：3 维超立方体以及对应于 3 位格雷码的哈密顿路径。

你可能想知道在该路径上顶点 $0^n$（$n$ 个零）和 $1^n$（$n$ 个一）之间有多少个顶点。显然，它会在 $2^{n-1}-1$ 和 $2^n-2$ 之间，因为通常 $0^n$ 是第一个顶点，而 $1^n$ 位于路径的后半部分。在找到这个问题的优雅答案后，你问自己是否可以通过编写一个程序来推广这个答案，该程序可以确定超立方体中任意两个顶点之间，在对应于格雷码的路径上的顶点数量。

输入格式

输入包含一行，包含： 一个整数 $n$ ($1 \le n \le 60$)，表示超立方体的维度 两个二进制字符串 $a$ 和 $b$，长度均为 $n$，其中 $a$ 在 $n$ 位格雷码中出现在 $b$ 之前。

输出格式

输出 $n$ 位格雷码中 $a$ 和 $b$ 之间的码字数量。

样例

样例输入 1

3 001 111

样例输出 1

3

样例输入 2

3 110 100

样例输出 2

2