小葱的01串

题号：NC230830
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为偶数的环形 01 字符串。（环形指，第一个字符和最后一个字符是相邻的）

字符串初始每个字符都是白色。小葱想把一段连续区间染成红色，使得红色的字符'0'数量等于白色的字符'0'数量，红色的字符'1'数量等于白色的字符'1'数量。问有多少种不同的染色方法？

两个方案不同当且仅当存在一个某字符，在一个方案是染成红色，在另一个方案为白色。

第一行输入一个正整数 ，代表字符串长度。
第二行输入一个长度为  的 01 字符串（仅由字符'0'和字符'1'组成的字符串）
数据范围：
 。保证  是偶数。

合法的染色方案数。

示例1

复制

2
11

复制

将第一个数字染红为一个方案。
将第二个数字染红为一个方案。

示例2

复制

4
0101

复制

任意一个长度为2的区间染红均合法。

示例3

复制

4
1100

复制

可以将区间 [2,3] 染红，或者将第一个和最后一个字符染红（因为是个环，所以第一个和最后一个也是相邻区间）。