Pretty chocolate and number game

Coco is playing with white and dark chocolate pieces as usual. A chocolate array is a one-dimensional arrangement of white and dark chocolate pieces. Let's call a chocolate array containing $N$ white and $N$ dark pieces pretty if it satisfies the following. $white$ and $dark$ denote a single white and dark piece respectively, $pretty$ is a pretty chocolate array, and $(X_1, X_2, \cdots, X_n)$ is the concatenation of chocolate arrays $X_1, X_2, \cdots, X_n$.

• $(white, dark)$ is pretty.
• $(white, pretty, dark)$ is pretty.

The score of a chocolate array is calculated as follows. Start with an integer $a$. Then, for each chocolate from left to right, add $b$ if it is white, and multiply $c$ if it is dark. Finally, take the remainder modulo $10^5$.

Coco wants to find the pretty chocolate array with the highest score. Calculate the score of the best-scoring pretty chocolate array.

The first line of input contains the integers $N$, $a$, $b$, and $c$, separated by spaces. ($1 \le N \le 15$, )

Output the highest score achievable with a pretty chocolate array containing $N$ white and $N$ dark chocolate pieces.