SP33048 FINDLR - Find Linear Recurrence

You are given the first $ 2K $ integers $ a_0, a_1, \ldots, a_{2K-1} $ (modulo $ M $ ) of an infinite integer sequence $ (a_i)_{i=0}^{\infty} $ that satisfies an integer-coefficient linear recurrence relation of order $ K $ . That is, they satisfy $$ a_n = \sum_{i=1}^{K} c_i a_{n-i} $$ for $ n \ge K $ , where $ c_1, \ldots, c_K $ are integer constants. Find $ a_{2K} $ modulo $ M $ .

The first line contains $ T $ ( $ 1 \le T \le 4000 $ ), the number of test cases. Each test case consists of two lines: - First line contains $ K $ ( $ 1 \le K \le 50 $ ) and $ M $ ( $ 1 \le M

For each test case, output $ a_{2K} $ modulo $ M $ .