{"code":"twice7","name":"TWICE7 (Normal)","description":"Một dãy  **FIBONACCI**  được định nghĩa như sau:  $F_0  =  F_1  =  1$;  $F_N = F_{N-1} + F_{N-2}$   $∀$  $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}$  $∀$  $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#### 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#### Output\r\n- Gồm $N$ dòng, mỗi dòng là $D_{p_k}$  modulo  $10^9+7$.\r\n\r\n#### Scoring\r\n\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    ???+ \"Input\"\r\n        ```sample\r\n        4\r\n        4 1 1 5 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        2\r\n        1\r\n        2\r\n        ```\r\n    ??? warning \"Note\"\r\n\r\n        -   $p_1$  =  $F_4$  = 5\r\n        -   $p_2$  =  $F_4$  +  $F_1$  = 5 + 1 = 6\r\n        -   $p_3$  =  $F_4$  +  $F_1$ + $F_1$  = 5 + 1 + 1 = 7\r\n        -   $p_3$  =  $F_4$  +  $F_1$ + $F_1$  +  $F_5$  = 5 + 1 + 1 + 8 = 15\r\n\r\n        Vậy ta có:\r\n\r\n        -   $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        -   $D_{P_2}$  = 2 (vì 6 = 1 + 5 = 1 + 2 + 3)\r\n        -   $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        -   $D_{P_4}$  = 2 (vì 15 = 2 + 13 = 2 + 5 + 8)","points":600.0,"partial":true,"time_limit":3.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}}