Fibonacci numbers have the following form:

We have an array which contains elements.

We want to find .

Input Format
The first line contains , where denotes size of the array.
Each of the next lines contains a number: the line contains .

Output Format
Print a single integer — the remainder of the division of the resulting number by .

Constraints

Sample Input 1

3
2
3
5

Sample Output 1

1

Explanation 1

Sample Input 2

2
3
6

Sample Output 2

2

Explanation 2