{"code":"beautiq","name":"Số BEAUTIQ","description":"Cho một số $X$. Ta gọi $BQ(X)$ là số BeautiQ thứ $X$.\r\n\r\nSố BeautiQ được xác định qua công thức như sau:\r\n\r\n- $BQ(0)=A,BQ(1)=B$, với $A,B$ cho trước.\r\n- $BQ(X)=BQ(X−1)+BQ(X−2)+BQ(X−1) \\times BQ(X−2). \\ (X \\geq 2)$\r\n\r\nCho $Q$ truy vấn, truy vấn thứ $i$ gồm 3 số nguyên dương $N_i,A_i,B_i$. Với truy vấn thứ $i$, tính $BQ(N_i)$ $mod$ $(10^9+7)$ với $BQ(0)=A_i,BQ(1)=B_i$.\r\n\r\n#### Input \r\n- Dòng đầu tiên chứa số nguyên dương $Q$ là số truy vấn.\r\n- $Q$ dòng tiếp theo, dòng thứ $i$ chứa 3 số nguyên dương $N_i,A_i,B_i$ thể hiện cho truy vấn thứ $i$.\r\n\r\n#### Output\r\n- Ghi ra $Q$ dòng, dòng thứ $i$ là kết quả cho truy vấn thứ $i$.\r\n#### Scoring\r\n\r\n- Subtask $1$ ($30\\%$ số điểm): $Q \\leq 10^2;N_i,A_i,B_i \\leq 5 \\times 10^5$.\r\n- Subtask $2$ ($70\\%$ số điểm): $Q \\leq 10^4;N_i \\leq 10^{18};A_i,B_i \\leq 10^{12}$\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2\r\n        5 1 1\r\n        4 2 5 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        255\r\n        1943\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}}