Fibonacci numbers have the following form:
We have an array which contains elements.
We want to find .
The first line contains , where denotes size of the array.
Each of the next lines contains a number: the line contains .
Print a single integer — the remainder of the division of the resulting number by .
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2