这天，小X和同伴们来到大西洋的一个荒岛上。据说，这里有巨额财宝，他们决心找出这座宝藏。在费尽了心思之后，小X们终于来到了宝藏的门前。大门是金属材料制成的，没有密码是不可能打开它的。幸运的是，小X们有这么一条线索：密码是一个有一定规律的数列的第N个数，这个数列从第四个数开始每个数都是前三个数的和；不幸的是，N可能很大，仅凭小X们是不可能完成这个任务的。现在，小X们需要你帮助他完成这项任务。你的任务是利用程序帮助小X找到第N个数。

第一行：一个数N（4≤N≤7000）。 第二行：这个数列的第一个数。 第三行：这个数列的第二个数。 第四行：这个数列的第三个数。 以上三行的数均<=2*10^9.

一行：第N个数。这个数一定不超过3000位。

5
1
1
2

7