# Counting Good Binary Strings
## Problem Statement
A binary string is defined as "good" if it satisfies the following two conditions:
1. Every block of consecutive `0`s in the string has a length of exactly $a$.
2. Every block of consecutive `1`s in the string has a length of exactly $b$.
For example, if $a=2$ and $b=3$, then `0011100` is a good binary string. The string `00110` is not good because the second block of `0`s has length $1$, not $a=2$. The string `000111` is not good because the first block of `0`s has length $3$, not $a=2$. Note that a string consisting only of `0`s (e.g., `0^a`) or only of `1`s (e.g., `1^b`) is considered good, as the condition for the absent character is vacuously true.
You are given four positive integers: $a$, $b$, $mn\_len$, and $mx\_len$. Your task is to find the total number of distinct good binary strings whose length $L$ satisfies $mn\_len \le L \le mx\_len$.
## Input Format
The first and only line of input contains four integers $a$, $b$, $mn\_len$, and $mx\_len$, separated by spaces.
- $1 \le a, b \le 10^9$
- $1 \le mn\_len \le mx\_len \le 10^{18}$
## Output Format
Output a single integer representing the total count of good binary strings that meet the criteria.
## Sample Test Cases
### Sample Input 1
```
1 2 1 10
```
### Sample Output 1
```
13
```
### Sample Input 2
```
3 3 1 100
```
### Sample Output 2
```
66
```
## Constraints
- $1 \le a, b \le 10^9$
- $1 \le mn\_len \le mx\_len \le 10^{18}$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1:
#### $a=1, b=2, mn\_len=1, mx\_len=10$
Since $a \ne b$, we consider three categories of good binary strings with distinct lengths:
1. Strings starting and ending with '0': These are of the form $(0^a (1^b 0^a)^m)$ for $m \ge 0$. Their lengths are $a + m(a+b)$.
For $a=1, b=2$, lengths are $1 + m(3)$.
For $m=0, L=1$ (`0`).
For $m=1, L=4$ (`0110`).
For $m=2, L=7$ (`0110110`).
For $m=3, L=10$ (`0110110110`).
There are $4$ such strings in the range $[1, 10]$.
2. Strings starting and ending with '1': These are of the form $(1^b (0^a 1^b)^m)$ for $m \ge 0$. Their lengths are $b + m(a+b)$.
For $a=1, b=2$, lengths are $2 + m(3)$.
For $m=0, L=2$ (`11`).
For $m=1, L=5$ (`11011`).
For $m=2, L=8$ (`11011011`).
There are $3$ such strings in the range $[1, 10]$.
3. Strings starting with '0' and ending with '1', OR starting with '1' and ending with '0': These are of the form $((0^a 1^b)^m)$ or $((1^b 0^a)^m)$ for $m \ge 1$. Their lengths are $m(a+b)$.
For $a=1, b=2$, lengths are $m(3)$.
For $m=1, L=3$ (`011` and `110`).
For $m=2, L=6$ (`011011` and `110011`).
For $m=3, L=9$ (`011011011` and `1100110011`).
For each of these $3$ lengths, there are $2$ distinct strings. Total $3 \times 2 = 6$ strings.
The total count is $4 + 3 + 6 = 13$.
### Sample 2:
#### $a=3, b=3, mn\_len=1, mx\_len=100$
Since $a=b=3$, any good binary string must have a length that is a multiple of $a$. For any length $L = k \cdot a$ where $k \ge 1$, there are always two distinct good binary strings: one starting with '0' and one starting with '1'.
For example:
- Length $3$: `000` and `111`.
- Length $6$: `000111` and `111000`.
- Length $9$: `000111000` and `111000111`.
We need to find the number of integers $k$ such that $mn\_len \le k \cdot a \le mx\_len$.
Given $a=3, mn\_len=1, mx\_len=100$:
$1 \le k \cdot 3 \le 100$
The minimum $k$ is $\lceil 1/3 \rceil = 1$.
The maximum $k$ is $\lfloor 100/3 \rfloor = 33$.
The number of possible $k$ values is $33 - 1 + 1 = 33$.
Since each valid length $k \cdot a$ corresponds to $2$ distinct good binary strings, the total count is $33 \times 2 = 66$.
Loading problem statement...