{"code":"22_tht_khuvucmienbac_b_2","name":"Thay đổi màu","description":"Lê xếp $n$ hạt cườm thành một vòng tròn theo chiều kim đồng hồ, ban đầu, các hạt có mã màu lần lượt tương ứng là $a_1 = 0, a_2 = 0,..., a_n = 0$. Lê có hai loại lệnh để thay đổi mã màu như sau:\r\n\r\n - Lệnh ``D i``, gấp đôi mã màu của một hạt, cụ thể: $a_i = a_i \\times 2$, lệnh này chỉ được thực hiện nếu $a_i > 0$.\r\n - Lệnh ``P i``, gấp đôi và thêm $1$ và mã màu của hai hạt kề nhau, cụ thể: $a_i = a_i \\times 2 + 1$ và $a_j = a_j \\times 2 + 1$, trong đó $j$ là hạt kề tiếp theo của hạt $i$ theo chiều kim đồng hồ.\r\n\r\nLê muốn tìm cách thay đổi dãy mã màu ban đầu (tất cả đều bằng $0$) về trạng thái yêu thích bằng cách dùng hai loại lệnh trên.\r\n\r\n**Yêu cầu:** Cho dãy số nguyên không âm $b_1,b_2,...,b_n$, hãy giúp Lê đếm số cách thay đổi dãy mã màu ban đầu về dãy mã màu $b_1,b_2,...,b_n$ (hai cách được gọi là khác nhau nếu số bước sử dụng khác nhau hoặc ở bước thứ $t$ của cách này sử dụng lệnh khác với lệnh thứ $t$ của cách kia).\r\n\r\n#### Input\r\n\r\n - Dòng đầu tiên gồm số nguyên $n$.\r\n - Dòng thứ hai chứa $n$ số nguyên không âm $b_1,b_2,...,b_n$.\r\n\r\n#### Output\r\n\r\n - Một dòng chứa một số là phần dư khi chia số cách thực hiện được cho $10^9+7$.\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($25\\%$ số điểm): $n = 3, b_i \\le 3$.\r\n - Subtask $2$ ($25\\%$ số điểm): $n = 3, b_i \\le 30$.\r\n - Subtask $3$ ($25\\%$ số điểm): $n \\le 5, b_i \\le 1000$.\r\n - Subtask $4$ ($25\\%$ số điểm): $n \\le 5, b_i \\le 10000$.\r\n\r\n#### Example\r\n\r\n???+ question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        1 3 2\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":2100.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"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}}