A fantastic sequence ai is defined in the following way: a0, . . . , ak−1 are given integers, and the subse- quent elements are defined by the linear recurrence relation () ∑k cian−1 + ck+1 · (n ≥ k) You have to find an mod m, where n and m are given. an = Herec1,...,ck+1 areknownintegers. i=1 The first line of the input contains the number of the test cases, which is at most 20. The descriptions of the test cases follow. The first line of a test case description contains three integers k (0 ≤ k ≤ 20), m (1 ≤ m < 231), and n (0 ≤ n < 231) separated by spaces. The second line contains the integers c1,...,ck+1 separated by spaces (−231 ≤ ci < 231). The third line contains the integers a0,...,ak−1 separated by spaces (−231 ≤ ai < 231). The test cases are separated by blank lines. Output For each test case in the input, output one nonnegative integer: an mod m. Print a blank line between test cases. Sample Input 1 2 10 10 110 11 Sample Output 9 Input