思路：组合数学 乘法逆元 快速幂

首先我们考虑，对于一个0，如果它只有左侧或者右侧某一侧有1，那么它只能被这一侧的1消灭，因此对应的方案数为1

如果对于两侧都有1的0，我们其实是需要考虑连续的一段0

比如下面这个例子10010001

有两段连续的0的子串，一个含有2个0，一个含有3个0，我们单独考虑每一段0

题目描述

霍去病改革下的汉军骑兵，身披甲胄，手持长矛，以冲锋形态向匈奴军队进行无畏冲刺，这是汉荡平匈奴的一大成因。现在你置身广阔的草原，手下的骑兵和匈奴骑兵共$n$个人已然混作一团，但在霍将军看来，实际上只是一字排开。现在塔子模拟了一个游戏，你需要指挥骑兵作战。我们假设这一排人中有你的大汉的骑兵，也有匈奴的骑兵，每一次指挥，你有两种选择：

$1.$如果第i个位置是汉军骑兵的，并且$i+1<n$，第$i+1$个位置是匈奴骑兵，那么你可以指挥汉军骑兵将其消灭，在第$i+1$个位置将自动生成一个你的骑兵。（游戏嘛，never mind）

$2.$如果第i个位置是汉军骑兵的，并且$i-1>0$，第$i-1$个位置是匈奴骑兵，那么你可以指挥汉军骑兵将其消灭，在第$i-1$个位置将自动生成一个你的骑兵。（游戏嘛，never mind）

你必然可以调度过程中生成的你的骑兵！

如此看来，胜利是必然的，但是塔子出品，必属精品，你需要回答有多少种击杀顺序，可以把所有匈奴骑兵都消灭。

输入描述

第一行一个整数n，表示骑兵的数量。 第二行一个字符串$s$，表示初始时哪些格子是汉军骑兵。如果第i个位置是汉军骑兵,那么$s_i$=1，否则$s_i$=0。$1<n<10^5$

输出描述

输出一个整数，表示答案对 $10^9+ 7$ 取模的结果

样例

输入

5
01100

输出

3

说明

可能的击杀所有匈奴骑兵的顺序是，[0,3,4],[3,0,4],[3,4,0]

Limitation

1s, 1024KiB for each test case.