{"problem":{"name":"「WHOI-2」D&D","description":{"content":"给定**不重**集合 $A$，定义其 _装饰子集_  $$f(A)=\\{a\\in A|\\forall b\\in A-\\{a\\},a|b\\not= b \\}$$ 这里的 $\\texttt{“|”}$ 表示按位或；这里 $b\\in A-\\{a\\}$ 表示 $b\\in A$ 且 $b\\not=a$。 miku 有一个长度为 $n$ 的正整数序列 $a_i$。你要给这个序列连续地划分为若干个（至少一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8434"},"statements":[{"statement_type":"Markdown","content":"给定**不重**集合 $A$，定义其 _装饰子集_ \n\n$$f(A)=\\{a\\in A|\\forall b\\in A-\\{a\\},a|b\\not= b \\}$$\n\n这里的 $\\texttt{“|”}$ 表示按位或；这里 $b\\in A-\\{a\\}$ 表示 $b\\in A$ 且 $b\\not=a$。\n\nmiku 有一个长度为 $n$ 的正整数序列 $a_i$。你要给这个序列连续地划分为若干个（至少一个）连续子串。要求这些连续子串元素所组成的**不重集合**的 _装饰子集_ 相同。\n\n求方案数对 $10^9+7$ 取模。\n\n## Input\n\n第一行一个正整数表示 $n$。\n\n接下来长度为 $n$ 的正整数序列表示 $a_i$。\n\n## Output\n\n一行一个正整数表示答案。\n\n[samples]\n\n## Background\n\n有没有发现少了什么？\n\n我们的 miku 决定出门逛街了。但是好巧不巧的就是她家里的装饰物少的可怜，并且只有一些数字可以作为装饰。\n\n但是 miku 发现如果有若干个装饰物组成的数集 $A$，那么 $A$ 的子集 $f(A)$ 是最好看的（尽管不知道为什么）。所以就有了这道题。\n\n但是因为看到了标题，所以聪明的你应该知道 miku 要去哪里了（误）。\n\n## Note\n\n**【样例#1解释】** 可以证明，两种方法分别是：\n$$[1,2,3,4,5,5,4,3,2,1]$$\n$$[1,2,3,4,5],[5,4,3,2,1]$$\n\n这里三个子集所组成的不重集合都是 $\\{1,2,3,4,5\\}$。它们的装饰子集都是 $\\{3,5\\}$。具体说明如下：\n\n- $1:1|3=3$，故不属于。\n- $2:2|3=3$，故不属于。\n- $3:3|1=3,3|2=3,3|4=7,3|5=7$，故属于。\n- $4:4|5=5$，故不属于。\n- $5:5|1=5,5|2=7,5|3=7,5|4=5$，故属于。\n\n---\n**本题采用捆绑测试**\n\n- $\\text{subtask1(5pts)}:n\\leq10$。\n- $\\text{subtask2(10pts)}:a_i\\leq7$。\n- $\\text{subtask3(20pts)}:a_i=2^a+2^b$。其中 $a\\not = b$。\n- $\\text{subtask4(20pts)}:a_i=2^a+2^b$。其中不保证 $a\\not =b$。\n- $\\text{subtask5(10pts)}:$ 保证 $a_i$ 随机生成。\n- $\\text{subtask6(35pts)}:$ 无特殊限制。时限为 $3s$。\n\n对于 $100\\%$ 的数据，保证 $1\\leq n\\leq 3\\times10^6,0\\leq a_i\\leq2\\times 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8434","tags":["动态规划 DP","搜索","数学","二分","洛谷原创","O2优化","位运算","双指针 two-pointer"],"sample_group":[["10\n1 2 3 4 5 5 4 3 2 1","2"],["9\n1 2 2 1 1 1 2 2 1","16"]],"created_at":"2026-03-03 11:09:25"}}