Problem Statement

Count Good Binary Strings A binary string is a string made only of the characters 0 and 1 . Split a binary string into its maximal runs — the longest stretches of equal characters. A binary string is called good when every maximal run of 1 s has a length that is a multiple of one_group , and every maximal run of 0 s has a length that is a multiple of zero_group . Equivalently, a good string is exactly one that can be built by writing down blocks one after another, where each block is either one_group copies of 1 or zero_group copies of 0 . Several blocks of the same character may sit next to each other: with zero_group = 2 the string 0000 is good, because it is two blocks of 00 . You are given min_length , max_length , one_group and zero_group . Count the good binary strings whose length lies in [min_length, max_length] and report that count modulo 10^9 + 7 . Input Format Four lines, one integer on each: line 1: min_length line 2: max_length line 3: one_group line 4: zero_group Output