All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Partitioning binary strings
Tag(s):

Algorithms, Applications of Dynamic Programming, Dynamic Programming, Dynamic programming

Problem
Editorial
Analytics

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:

  1. 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.
  2. 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.
  3. 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\)

SAMPLE INPUT
6 101110
SAMPLE OUTPUT
3
Explanation

The three valid partitions are 101110, 10|1110, 101|110.

Time Limit: 2,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Circuits '19

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?