{"code":"matmul_4","name":"Recursive Sequence","description":"Cho dãy $a_i$ được định nghĩa như sau:\r\n\r\n$$\r\na_i = b_i \\ \\forall i \\le k\r\n$$\r\n\r\nVà\r\n\r\n$$\r\na_i = c_1 a_{i - 1} + c_2 a_{i - 2} + ... + c_k a_{i - k}\r\n$$\r\n\r\nCho hai dãy $b$ và $c$, hãy tính phần tử thứ $n$ của dãy $a$ khi lấy dư cho $10^9$.\r\n\r\n#### Input\r\n - Dòng đầu tiên chứa số nguyên $T$ $(T \\le 1000)$ là số lượng bộ test.\r\n - Mỗi test được input theo quy tắc sau:\r\n     - Dòng đầu là số nguyên dương $k$ $(k \\le 10)$.\r\n     - Dòng thứ hai là $k$ số $b_1, b_2, \\ldots, b_k$ $(0 \\le b_i \\le 10^9)$.\r\n     - Dòng thứ ba là $k$ số $c_1, c_2, \\ldots, c_k$ $(0 \\le c_i \\le 10^9)$.\r\n     - Dòng cuối cùng là số nguyên dương $n$ $(1 \\le n \\le 10^9)$.\r\n\r\n\r\n#### Output\r\n - Gồm $T$ dòng là đáp án cho các test.\r\n\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        3\r\n        3\r\n        5 8 2\r\n        32 54 6\r\n        2\r\n        3\r\n        1 2 3\r\n        4 5 6\r\n        6\r\n        3\r\n        24 354 6\r\n        56 57 465\r\n        98765432\r\n        ```\r\n    ??? success \"Output\"\r\n        ```\r\n        8\r\n        714\r\n        257599514\r\n        ```","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}