A balanced binary string is a binary string with an equal number of ~1~s and ~0~s. Given a string ~S~ of length ~N~, output the number of subsequences of ~S~ that are balanced binary strings, modulo ~10^{9}+7~.

A subsequence is defined as a sequence that can be derived from the string by deleting some or no elements. For this problem, an empty subset is not considered a subsequence.

Input Specification

The first line contains an integer, ~N (1 \leq N \leq 10^{5})~.

The second line contains a binary string, ~S~.

Output Specification

Output one integer, the number of subsequences of ~S~ that are balanced binary strings, modulo ~10^{9}+7~.

Subtasks

Subtask 1 [10%]

~0 < N \le 20~

Subtask 2 [90%]

~0 < N \le 10^5~

Sample Input

5
10010

Sample Output

9