题目描述

金克斯在希尔科的蛊惑之下已经不再轻易相信任何人包括她的姐姐蔚，但是金克斯心中十分怀念小时候的美好并给蔚一个机会与蔚玩了一场游戏。

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

字符串初始每个字符都是白色。蔚可以使用强能冲拳使一段连续区间染成红色。

而她必须使得红色的字符'0'数量等于白色的字符'0'数量，红色的字符'1'数量等于白色的字符'1'数量。

作为双城之战的忠实粉丝的你一定知道蔚可以使用多少种不同的染色方法吧！！

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

输入格式

第一行输入一个正整数 $n$，代表字符串长度。

第二行输入一个长度为 $n$ 的 $01$ 字符串（仅由字符'0'和字符'1'组成的字符串）

输出格式

一个整数代表蔚可以采用的办法。

样例

输入样例1

2
11

输出样例1

2

输入样例2

4
0101

输出样例2

4

数据范围与提示

$2 \leq n \leq 300000$,保证 $n$ 是偶数。

样例1解释

强能冲拳任意区间长度为$1$的区间

样例2解释

强能冲拳任意区间长度为$2$的区间