Extended Hundred Chickens Problem

The classic "Hundred Chickens" problem inspires this extension. In the original problem, each rooster costs $$5$$ yuan, each hen costs $$3$$ yuan, and every group of $$3$$ chicks costs $$1$$ yuan. Given $$100$$ yuan to buy $$100$$ chickens, one had to find a valid combination.

In this extended version, you are given the following parameters:

• Each rooster costs $$x$$ yuan.
• Each hen costs $$y$$ yuan.
• Every group of $$z$$ chicks costs $$1$$ yuan (note that the number of chicks must be a multiple of $$z$$).
• You have a total of $$n$$ yuan.
• You need to buy exactly $$m$$ chickens in total.

Your task is to determine the number of different ways (nonnegative integer solutions for the number of roosters, hens, and chicks) to buy exactly $$m$$ chickens with exactly $$n$$ yuan such that the cost equation holds:

$$x \cdot r + y \cdot h + \frac{c}{z} = n$$

with the additional constraint:

$$r + h + c = m$$

and the number of chicks $$c$$ must be a multiple of $$z$$.

inputFormat

The input consists of a single line containing five integers separated by spaces:

$$n\; m\; x\; y\; z$$

where

• $$n$$: total amount of money.
• $$m$$: total number of chickens to buy.
• $$x$$: cost per rooster.
• $$y$$: cost per hen.
• $$z$$: the number of chicks in one group, which costs $$1$$ yuan.

outputFormat

Output a single integer representing the number of valid buying schemes.

sample

100 100 5 3 3

1