## LCC '21 Contest 1 S3 - Balanced Binary Strings

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

A balanced binary string is a binary string with an equal number of s and s. Given a string of length , output the number of subsequences of that are balanced binary strings, modulo .

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, .

The second line contains a binary string, .

#### Output Specification

Output one integer, the number of subsequences of that are balanced binary strings, modulo .

5
10010
9