Consider recurrent functions of the following form: f(n)=a1f(n−1)+a2f(n−2)+a3f(n−3)+...+adf(n−d), forn>d, where a1, a2, ..., ad are arbitrary constants. A famous example is the Fibonacci sequence, defined as: f(1) = 1, f(2) = 1, f(n) = f(n − 1) + f(n−2). Hered=2,a1 =1,a2 =1. Every such function is completely described by specifying d (which is called the order of recurrence), values of d coefficients: a1, a2, ..., ad, and values of f(1), f(2), ..., f(d). You’ll be given these numbers, and two integers n and m. Your program’s job is to compute f(n) modulo m. Input Input file contains several test cases. Each test case begins with three integers: d, n, m, followed by two sets of d non-negative integers. The first set contains coefficients: a1, a2, ..., ad. The second set gives values of f(1), f(2), ..., f(d). Youcanassumethat: 1≤d≤15,1≤n≤231−1,1≤m≤46340. Allnumbersintheinputwill fit in signed 32-bit integer. Input is terminated by line containing three zeroes instead of d, n, m. Two consecutive test cases are separated by a blank line. Output For each test case, print the value of f (n)( mod m) on a separate line. It must be a non-negative integer, less than m. Sample Input 1 1 100 2 1 2 10 100 11 11 3 2147483647 12345 12345678 0 12345 123 000 Sample Output 1 55 423