You are given a binary string of \(0s\) and \(1s\).

Your task is to calculate the number of ways so that a string can be partitioned by satisfying the following constraints:

The length of each partition must be in non-decreasing format. Therefore, the length of the previous partition must be less than or equal to the length of the current partition.
The number of set bits in each partition must be in non-decreasing format. Therefore, the number of 1's that are available in the previous partition must be less than or equal to the number of 1's that are available in the current partition.
There should be no leading zeroes available in each partition.

For example, the string \(101100\) contains \(10|1100\) , \(101100\) as the two valid partitions whereas \(10|1|100\), \(1|0|1100\) as some of the invalid partitions.

Note: The string as a whole is a valid partition.

Print the number of ways modulo \(1e9 + 7\).

Input format

The first and only line contains \(n\) and \(s\) that represents the length of the string and binary string.

Output format

Print the number of ways to partition the binary string.

Constraints

\(n \le 5000\)