Coco 正在玩白巧克力和黑巧克力。当排列 $N$ 个白巧克力和 $N$ 个黑巧克力时，满足以下条件的排列被称为“漂亮巧克力”。$(X,Y)$ 表示将巧克力排列 $X$ 和 $Y$ 按顺序拼接在一起。

• (白巧克力, 黑巧克力) 是漂亮巧克力。
• (白巧克力, 漂亮巧克力, 黑巧克力) 是漂亮巧克力。
• (漂亮巧克力, 漂亮巧克力) 是漂亮巧克力。
• 无法通过上述三条规则生成的巧克力排列不是漂亮巧克力。

某种巧克力排列的“得分”计算如下：从给定的整数 $a$ 开始，从左到右依次处理，如果遇到白巧克力，则加上 $b$；如果遇到黑巧克力，则乘以 $c$。最后得到的值对 $10^5$ 取模的结果即为该巧克力排列的得分。

Coco 想要在所有漂亮巧克力中找到得分最高的巧克力排列。请帮 Coco 计算出可以获得的最大得分。

输入格式

第一行按顺序给出整数 $N$，$a$，$b$，$c$。

输出格式

输出一行，表示使用 $N$ 个白巧克力和 $N$ 个黑巧克力可以制成的所有漂亮巧克力中，得分的最大值。

样例

输入样例 1

1 3 5 7

输出样例 1

56

输入样例 2

2 3 5 7

输出样例 2

637

输入样例 3

2 10 10 100

输出样例 3

1000

说明

$1 \le N \le 15$, $1 \le a, b, c \lt 10^5$