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$