Counting Block Arrangements with Multiplicative Row Constraint

Little Blue has an unlimited number of identical cubic blocks. He wants to arrange them on the ground to form a gigantic pattern. He places the blocks in n rows, with the blocks in each row aligned on the left.

The first row has exactly w blocks, i.e. H₁ = w. Starting from the second row, the number of blocks in the i-th row, H_i, satisfies the following condition:

where L and R are given integers, and note that when L = 0, it is allowed for consecutive rows to have the same number of blocks.

You are also given three integers: x, y and z (with 1 \le x < y \le n). Count the number of arrangements (i.e. sequences \(H_1, H_2, \dots, H_n\)) that satisfy all the conditions and, in addition, the number of blocks in row y is exactly z times the number of blocks in row x, i.e.:

Input Format: The input consists of two lines. The first line contains four space‐separated integers: n w L R. The second line contains three space‐separated integers: x y z.

Output Format: Output a single integer representing the number of valid arrangements.

Note: It is guaranteed that the input satisfies the conditions necessary for a valid arrangement, and you may assume that the constraints are small enough to allow a dynamic programming solution.

inputFormat

The first line contains four integers n, w, L, R, representing the number of rows, the number of blocks in the first row, and the minimum and maximum additional blocks to add to the previous row, respectively.

The second line contains three integers x, y, z (1 <= x < y <= n), where the arrangement must satisfy the condition that the number of blocks in the y-th row is exactly z times the number of blocks in the x-th row.

outputFormat

Output a single integer: the number of valid arrangements that satisfy the given conditions.

sample

3 1 0 1
1 3 2

2