Untitled

class Solution {
    private static final int MOD = 1_000_000_007;
    private int low, high, zero, one;
    private int[] memo;

    public int countGoodStrings(int low, int high, int zero, int one) {
        this.low = low;
        this.high = high;
        this.zero = zero;
        this.one = one;
        this.memo = new int[high + 1]; // Memoization array
        Arrays.fill(memo, -1); // Initialize with -1 (uncomputed)

        return solve(0); // Start with an empty string (length 0)
    }

    private int solve(int len) {
        // Base case: if length exceeds high, return 0
        if (len > high) {
            return 0;
        }

        // If already computed, return the stored result
        if (memo[len] != -1) {
            return memo[len];
        }

        // Count the current string if its length is within [low, high]
        int count = (len >= low && len <= high) ? 1 : 0;

        // Append '0' zero times and recur
        count = (count + solve(len + zero)) % MOD;

        // Append '1' one times and recur
        count = (count + solve(len + one)) % MOD;

        // Store the result in the memoization array
        memo[len] = count;
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        int low1 = 3, high1 = 3, zero1 = 1, one1 = 1;
        System.out.println(solution.countGoodStrings(low1, high1, zero1, one1)); // Output: 8

        // Example 2
        int low2 = 2, high2 = 3, zero2 = 1, one2 = 2;
        System.out.println(solution.countGoodStrings(low2, high2, zero2, one2)); // Output: 5
    }
}