Coco is playing with white and dark chocolates. When $N$ white chocolates and $N$ dark chocolates are arranged, an arrangement is called a "pretty chocolate" if it satisfies the following conditions. $(X, Y)$ denotes the concatenation of chocolate arrangements $X$ and $Y$ in order.
- (white, dark) is a pretty chocolate.
- (white, pretty chocolate, dark) is a pretty chocolate.
- (pretty chocolate, pretty chocolate) is a pretty chocolate.
- Any chocolate arrangement that cannot be formed by the three rules above is not a pretty chocolate.
The "score" of a chocolate arrangement is calculated as follows: Starting from a specific integer $a$, for each chocolate from left to right, add $b$ if it is a white chocolate, and multiply by $c$ if it is a dark chocolate. The remainder of the final value when divided by $10^5$ is the score of the chocolate arrangement.
Coco wants to find the pretty chocolate arrangement with the highest score. Calculate the highest possible score for Coco.
The first line contains the integers $N$, $a$, $b$, and $c$ in order.
Output the maximum score of a pretty chocolate that can be made using $N$ white chocolates and $N$ dark chocolates on a single line.
Examples
Input 1
1 3 5 7
Output 1
56
Input 2
2 3 5 7
Output 2
637
Input 3
2 10 10 100
Output 3
1000
Note
$1 \le N \le 15$, $1 \le a, b, c \lt 10^5$