#184. 「10-4」D、青蛙棋盘[2] 暂未评定

青蛙棋盘是一排 n 个格子的棋盘，每个格子上有一个分数(整数)。

青蛙站在第 1 个格子上，她每一跳可向前跳跃 1、2 或 3 个格子，比如：青蛙站在第 1 个格子上，

向前跳跃 2 个格子后，会站在第 3 个格子上。青蛙自动获得第一个格子的分数，在以后的跳跃中每到达一

个格子，就获得该格子的分数。特别注意的是，青蛙在从 1 跳到 n 时，跳跃 1 个格子的次数为 x，跳跃 2

个格子的次数为 y，跳跃 2 个格子的次数为 z。

给出棋盘每个格子的分数和 x,y,z，请帮助青蛙计算从第 1 个格子跳到第 n 个格子的不同的跳法数

和所能获得的最大分数和。

第 1 行包含 3 个整数：n,x,y,z。注意：输入保证 x+2y+3z=n。 第 2 行包含 n 个整数 a[1]、a[2]、…、a[n]，其中 a[i]表示第 i 个格子的分数。

含两行，分别表示不同的跳法数和所能获得的最大分数。注意方案数可能很大，请 mod 后输出。

样例输入

D.in

12 2 2 2
6 10 11 2 8 3 4 5 7 9 1
90

样例输出

D.out

47

1<=N<=1000

1<=x,y,z<=300;

0<=a[i]<=100;