题目背景

小符同学最近在练习电吉他的即兴 Solo。为了让拨弦的旋律听起来既有规律又不失层次感，他发明了一种“递归旋律”的创作方法。你能用代码帮他生成出这套华丽的谱子吗？

题目描述

小符同学规定了旋律的生成法则如下：

• 1 级旋律仅包含一个音符字符：A
• 对于 $N$ 级旋律（$N > 1$），它的构成为：先弹奏一遍 $N-1$ 级旋律，接着弹奏字母表中的第 $N$ 个大写字母，最后再弹奏一遍 $N-1$ 级旋律。

例如：

• 1 级旋律：A
• 2 级旋律：A + B + A = ABA
• 3 级旋律：ABA + C + ABA = ABACABA

现给定一个整数 $N$，请编写一个递归程序，输出对应的 $N$ 级旋律。

输入格式

输入一个整数 $N$，满足 $1 \le N \le 15$。

输出格式

输出一个字符串，表示生成的 $N$ 级递归旋律。

样例

3

ABACABA

4

ABACABADABACABA