在可以炼制魔力强大的法杖的同时，Magic Land 上的人们渐渐意识到，魔力强大并不一定能给人们带来好处——反而，由此产生的破坏性的高魔力释放，给整个大陆蒙上了恐怖的阴影。
可控的魔力释放，成为了人们新的追求。这种控制魔力释放的技术，也就是被现在的我们熟知的“魔法”。在远古时期，“魔法”由法师们口口相传，但也因为这样，很多“古代魔法”已经成为传说——因为那时没有良好的记录魔法的方法。
后来，天才法师 Ferdinand 发现了一种记录魔法的方法：将一种特殊材料做成的正反面均有 $1$ 行 $N$ 列格子的带子的一端扭转 $180$ 度之后与另一端粘贴，这样就得到了一个仅有一面的环，被称为“符环” （Spell Ring）。
符环上的某一个格子为“起始位”，并标有起始方向，这样，我们就可以给这个环上的每一个格子进行编号： 起始位编号是 $0$，向起始方向移动一格为 $1$，这样，一共有 $2N$ 个格子，并且第 $i$ 个格子的背面（虽然带子是一面的，但是仍然有“背面”这个概念）是第 $(i+N) \bmod N$ 格。
法师们将魔法用一个由魔法标记 “（” 和 “）” 组成的串表示。人们发现，所有魔法对应的串都为合法的括号序列，并且任何一个合法的括号序列都对应一个魔法。可以发现，合法的括号序列长度均为偶数，这样就可以把一个魔法写在符环之中：从起始格开始，向起始方向，依次写入魔法标记。
这种特殊的材料使得符环带有美丽的色彩：假如一个格子的两面写有相同的魔法标记（即：假设这个带子是透明的，两个魔法标记重合），那么这个格子会变为绯红色（Scarlet）；反之，若两面的魔法标记不同，会变为深蓝色（Deep blue）。
现在，你得到了一些古代的符环，由于年代久远，魔法标记已经变得模糊不清，但是颜色依然保持完好。你希望知道：给定的颜色信息，对应了多少种不同的魔法？
Comet OJ