There are $n$ train cars standing on a one-dimensional track. Initially, no two cars are connected. In each move, you can connect two adjacent groups of connected cars, provided that the number of cars in these groups does not differ by more than $d$. The time taken for such a connection depends on the number of cars in the groups being connected. Your task is to connect all groups into a single train consisting of $n$ cars.

The cost of connecting a group of $w$ cars with a group of $v$ cars (provided $|w - v| \le d$) is given by the function $(aw + bv) \pmod{1001}$.

Input

The only line of input contains four positive integers $n$, $d$, $a$, and $b$ ($1 \le n \le 10^{16}$, $1 \le d, a, b \le 1000$).

Output

The only line of output should contain a single integer representing the minimum cost to connect all $n$ cars into one train.

Examples

Input 1

5 1 1 1

Output 1

12

Note

Explanation of the example: We connect the first car with the second (cost 2), the third with the fourth (cost 2), then with the fifth (cost 3), and finally we connect the two resulting groups of cars (cost 5).

Ocenianie