Cipher

Interview

Time limit2sMemory limit1024 MB

Summary

Count the original binary strings whose run-length encoding (each run's character followed by its decimal length) equals the given binary string, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, String, Prefix sum
Solved: No attempts yet

Statement

Moriarty is dead, but many followers remain. Yesterday one of them arrived in town carrying an important message. Watson and Holmes caught him, found a letter in his pocket, and questioned him.

The interrogation revealed that the letter contains an encrypted description of a sinister plan that Moriarty did not carry out before he died. Moriarty kept all information in binary code, as strings of zeros and ones. To encrypt a message describing the plan, he split the binary string into maximal groups of consecutive identical characters, then replaced each group with its character followed by the number of occurrences in the group. For example, 111 becomes 13, and 0000000000 becomes 010. So 11100 becomes 1302, and 00000000001 becomes 01011.

It is also known that the encrypted plan is itself a binary string. The professor sent exactly that string in the letter.

Nothing more is known about the message. Sherlock wants to know what was encrypted. Recovering it for certain is unlikely. So he asks for the number of original messages that would encrypt to the string Watson and Holmes intercepted. This number can be large, so output it modulo $1\,000\,000\,007$ .

Input

The first line contains one integer $n$ , the length of the intercepted message ( $1 \le n \le 100\,000$ ).

The second line contains the message, a string of length $n$ made of 0 and 1.

Output

Print the number of possible original messages modulo $1\,000\,000\,007$ on a single line.

Examples2

Example 1
Input
```
4
0111
```
Expected output
```
2
```
Example 2
Input
```
2
00
```
Expected output
```
0
```