D-举手赢棋hard_牛客周赛 Round 80

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为《举手赢棋easy》的困难版本，两题的唯一区别在于对举手次数的限制不同，在本题中，小红有 $\color{orange}{\pmb 2}$ 次举手的机会。

$\hspace{15pt}$ 小红获得了参加鹿瓜杯的资格，在赛前，她预测了接下来的 $n$ 场比赛，使用一个仅由 $\texttt{`0'}$ 和 $\texttt{`1'}$ 构成的字符串 $s$ 表示。其中， $s_i=\texttt{`0'}$ 代表第 $i$ 场比赛会失利， $s_i=\texttt{`1'}$ 代表第 $i$ 场比赛会胜利。
$\hspace{15pt}$ 为了胜利，小红希望任意时刻自己的胜场不低于负场。因此，小红有 $2$ 次通过“举手”强行获得一场比赛胜利的机会（即将字符串的任意一位修改为 $\texttt{`1'}$ ）。
$\hspace{15pt}$ 请你帮小红计算有多少种安排这 $2$ 次举手的方案。

$\hspace{15pt}$ 一个合法的方案需要满足：恰好有 $2$ 局是举手的，且任意时刻胜场数量不小于负场数量。
$\hspace{15pt}$ 请注意，小红在预测胜场的局也可以选择举手。

输入描述:

第一行输入一个正整数  代表比赛场数。 
第二行输入一个长度为 、仅由  和  构成的字符串 。其中， 代表在不举手的情况下，第  场比赛会失利， 代表在不举手的情况下，第  场比赛会胜利。

输出描述:

输出一个整数，代表有多少种安排这  次举手的方案。

示例1

输入

复制

7
0100000

输出

复制

说明

在这个样例中，无论小红怎么举手，都无法挽回口碑。

示例2

输入

复制

5
10110

输出

复制

说明

在这个样例中，任意选择两场举手均可。

示例3

输入

复制

5
01000

输出

复制

说明

在这个样例中，有以下三种可行的方案：
选择第一局、第三局举手；
选择第一局、第四局举手；
选择第一局、第五局举手。