该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

汉诺塔

时间限制：$1s$

空间限制：$256MiB$

题目描述

汉诺塔问题是一个十分经典的问题。

即有三根杆子 A, B, C。A 杆上有 n 个穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

1. 每次只能移动一个圆盘
2. 大盘不能叠在小盘上面

由于汉诺塔问题最优步骤实际上是需要 $2^n-1$ 步，可以证明每一步实际上是固定的。

所以小甘雨想要知道，对于某个状态而言，汉诺塔此时进行到第几部。

数据格式

输入

两行.

第一行, 一个正整数 n. 表示汉诺塔问题的规模 (圆盘的数量).

第二行, 一个长度为 n 的字符串 S. S仅包含 ABC, 第 i 个字符表示第 i 小的圆盘所在杆子的编号.

输出

一个正整数 k, 表示第 k 步的状态为 S.

由于数字比较大, 你需要输出 k 的二进制数, 不足 n 位的补 0, 参考样例1.

样例

输入 #1

3
BBA

输出 #1

011

输入 #2

5
CCCCC

输出 #2

11111

样例解释

样例1解释： 首先可以知道 $(011)_2$转成 10 进制后的数字为 3. 对于最优还原 3 层汉诺塔问题的解决步骤如下： $AAA \rarr CAA \rarr CBA \rarr BBA \rarr BBC \rarr ABC \rarr ACC \rarr CCC$ 从左往右每次依次为第 0, 1, 2, ..., 7 步后哈诺塔的情况。 可以证明该方案一定是最优方案。

其中, BBA是第 3 步, 输出 011.

数据范围及约定

对于测试点1-10, $10^2 \le n \le 10^5$

对于测试点11-20, $10^5 \le n \le 10^6$

对于测试点21, $n=10^7$.

对于测试点22, $n=10^8$.

对于所有测试点, 保证给出的字符串 S 是最优操作中的一步.