{"code":"seq16","name":"Recursive Sequence","description":"Cho dãy ($a_i$) các số tự nhiên được định như sau:\r\n- $a_i = b_i$ (với  $i \\le k$)\r\n- $a_i = c_1a_{i-1} + c_2a_{i-2} + ... + c_ka_{i-k}$ (với  $i > k$)\r\n\r\nVới $b_i$ và $c_i$ là các số tự nhiên cho trước ($1\\le i\\le k$). Hãy tính $a_n \\mod 10^9$, với $n$ cho trước.\r\n\r\n<h4>Input</h4>\r\n\r\n- Dòng đầu tiên chứa số $c$ là số lượng test ($1\\le c\\le 1000$). Mỗi test chứa 4 dòng:\r\n- Dòng 1: chứa số $k$, là số phần tử của dãy $c$ và $b$ ($1 \\le k \\le 10$)\r\n- Dòng 2: chứa các số $b_1,...,b_k$  với $0 \\le b_i \\le 10^9$, mỗi số cách nhau một dấu cách.\r\n- Dòng 3: chứa các số $c_1,...,c_k$  với $0 \\le c_i \\le 10^9$, mỗi số cách nhau một dấu cách.\r\n- Dòng 4: chứa số $n$ ($0 \\le n \\le 10^9$)\r\n\r\n<h4>Output</h4>\r\n\r\n- Gồm $c$ dòng, mỗi dòng là kết quả của một test, ghi giá trị: $a_n \\mod 10^9$\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\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    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        8 \r\n        714 \r\n        257599514\r\n        ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}