{"code":"subset","name":"Đếm tập con chẵn","description":"Cho dãy số $a_1, a_2, …, a_n$ và $q$ thao tác thuộc 1 trong 2 loại sau:\r\n\r\n`1 k b`: gán $a_k=b$\r\n\r\n`2 l r`: Tính số lương tập con $\\{k_1, k_2, ..., k_m\\}$ khác rỗng của tập $\\{l,l+1,…,r\\}$ sao cho $a_{k_1} + a_{k_2} + ... + a_{k_m}$ là số chẵn. \r\n \r\n**Yêu cầu:** Với thao tác loại 2,  hãy in ra số dư của kết quả khi chia cho $10^9+7$.\r\n\r\n#### Input\r\n+ Dòng đầu chứa 2 số nguyên $n,q$.\r\n+ Dòng tiếp theo chứa $n$ số $a_1,a_2,…,a_n (1\\leq a_i \\leq 10^9)$.\r\n\r\n+ $q$ dòng tiếp theo mỗi dòng chứa một trong hai loại thao tác :\r\n\r\n   + `1 k b` $(1 \\leq k \\leq n; 1 \\leq b \\leq 10^9)$\r\n   + `2 l r` $(1\\leq l \\leq r \\leq n)$\r\n\r\n#### Output\r\nVới mỗi thao tác loại $2$, in ra số lượng tập con thỏa mãn $(mod \\ 10^9+7)$  trên một dòng.\r\n\r\n#### Scoring\r\n - Subtask #1 ($20\\%$ số điểm): $n,q \\leq 20$.\r\n - Subtask #2 ($20\\%$ số điểm): $n,q \\leq 5000$.\r\n - Subtask #3 ($20\\%$ số điểm): $n \\leq 10^5, q \\leq 100$.\r\n - Subtask #4 ($40\\%$ số điểm): $n,q \\leq 10^5$.\r\n\r\n#### Example \r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 6\r\n        2 4 6 8 10\r\n        2 1 3\r\n        2 4 4\r\n        2 4 5\r\n        1 4 7\r\n        2 4 4\r\n        2 4 5\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        7\r\n        1\r\n        3\r\n        0\r\n        1\r\n        ```","points":400.0,"partial":true,"time_limit":2.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}}