{"code":"twice9","name":"TWICE9 (Super very hard)","description":"**Lưu ý: Bản này khác bản dễ ở time limit và memory limit, ai làm được có thưởng :v **\r\n\r\nMột dãy **FIBONACCI** được định nghĩa như sau: **$F_{0}$** = **$F_{1}$** = **1**; **$F_{N}$** = **$F_{N-1}$** + **$F_{N-2}$** *$\\forall$* $N$ > $1$.\r\n\r\nMột vài phần tử đầu của dãy là: 1,1,2,3,5,8,13,21,...\r\n\r\nVới mỗi số nguyên dương **p**, gọi **$D_{p}$** là số cách biểu diễn số **p** dưới dạng tổng các số **FIBONACCI** khác nhau.\r\n\r\nBạn được cho một mảng **A** gồm **N** phần tử. Với mỗi giá trị **k** = 1, 2, ..., N, ta định nghĩa $p_{k}$ = $F_{A_{1}}$ + $F_{A_{2}}$ + ... + $F_{A_{k}}$. Nhiệm vụ của bạn là hãy tính **$D_{p_{k}}$** $\\forall$ **k** = 1, 2, ..., N. Vì kết quả rất lớn nên đáp án cuối cùng là **$D_{p_{k}}$** modulo **$10^9$ + 7**\r\n\r\n#### Input\r\n - Dòng thứ nhất là số nguyên dương **N**, số phần tử của mảng **A**.\r\n - Dòng thứ hai gồm các số nguyên dương **$A_{1}$**, **$A_{2}$**, ..., **$A_{N}$**.\r\n\r\n#### Output\r\n - Gồm N dòng, mỗi dòng là *$D_{p_k}$* modulo **$10^9$ + 7**.\r\n#### Scoring\r\n- Subtask $1$ ($5\\%$ số điểm): **N**, $A_{i}$ $\\leq$ 15.\r\n- Subtask $2$ ($20\\%$ số điểm): **N**, $A_{i}$ $\\leq$ 100.\r\n- Subtask $3$ ($15\\%$ số điểm): **N** $\\leq$ 100, $A_{i}$ là số chính phương.\r\n- Subtask $4$ ($10\\%$ số điểm): **N** $\\leq$ 100, $A_{i}$ không có giới hạn gì thêm.\r\n- Subtask $5$ ($15\\%$ số điểm): $A_{i}$ là các số chẵn.\r\n- Subtask $6$ ($35\\%$ số điểm): **N** $\\leq$ $10^5$, $A_{i}$ $\\leq$ $10^9$\r\n####Example\r\n!!! question \"Test 1\"\r\n\t???+ \"Input\"\r\n\t\t```sample\r\n\t\t4\r\n\t\t4 1 1 5\r\n\t\t```\r\n\t???+ success \"Output\"\r\n\t\t```sample\r\n\t\t2\r\n\t\t2\r\n\t\t1\r\n\t\t2\r\n\t\t```\r\n\t??? warning \"Note\"\r\n\t\t- $p_{1}$ = $F_{4}$ = 5\r\n\t\t- $p_{2}$ = $F_{4}$ + $F_{1}$ = 5 + 1 = 6\r\n\t\t- $p_{3}$ = $F_{4}$ + $F_{1}$ + $F_{1}$ = 5 + 1 + 1 = 7\r\n\t\t- $p_{4}$ = $F_{4}$ + $F_{1}$ + $F_{1}$ + $F_{5}$ = 5 + 1 + 1 + 8 = 15\r\n\r\n\t\tVậy ta có: \r\n\t\t- $D_{p_{1}}$ = 2 (vì số 5 có thể biểu diễn bằng $F_{2}$ + $F_{3}$ hay đơn giản là $F_{4}$ )\r\n\t\t- $D_{p_{2}}$ = 2 (vì 6 = 1 + 5 = 1 + 2 + 3)\r\n\t\t- $D_{p_{3}}$ = 1 (vì số 7 chỉ có một cách biểu diễn duy nhất là 2 + 5)\r\n\t\t- $D_{p_{4}}$ = 2 (vì 15 = 2 + 13 = 2 + 5 + 8)","points":500.0,"partial":true,"time_limit":0.5,"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}}