有NNN个男女同学随机排成一队,老师决定取其中一段,要求这段的男女人数要一样多。问有多数种取法? 例如N=6N=6N=6,用1表示男生,用000表示女生,排队的情况是110001。可取方案有444段:1100、10001、10、01。
110001
1100
10001
10
01
输入格式
第一行111个正整数:NNN。NNN范围[1,1000000][1, 1000000][1,1000000]。 第NNN个整数FiF_iFi。Fi=1F_i=1Fi=1表示男生,Fi=0F_i=0Fi=0表示女生。
输出格式
一个整数,可分成的最多方案数。
输入输出样例
输入 #1
6 0 0 0 1 1 1
输出 #1
3