{"raw_statement":[{"iden":"statement","content":"You are given an array _s_ of _n_ non-negative integers.\n\nA 5-tuple of integers (_a_, _b_, _c_, _d_, _e_) is said to be valid if it satisfies the following conditions:\n\n*   1 ≤ _a_, _b_, _c_, _d_, _e_ ≤ _n_\n*   (_s__a_ | _s__b_) & _s__c_ & (_s__d_ ^ _s__e_) = 2_i_ for some integer _i_\n*   _s__a_ & _s__b_ = 0\n\nHere, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.\n\nFind the sum of _f_(_s__a_|_s__b_) * _f_(_s__c_) * _f_(_s__d_^_s__e_) over all valid 5-tuples (_a_, _b_, _c_, _d_, _e_), where _f_(_i_) is the _i_\\-th Fibonnaci number (_f_(0) = 0, _f_(1) = 1, _f_(_i_) = _f_(_i_ - 1) + _f_(_i_ - 2)).\n\nSince answer can be is huge output it modulo 109 + 7."},{"iden":"input","content":"The first line of input contains an integer _n_ (1 ≤ _n_ ≤ 106).\n\nThe second line of input contains _n_ integers _s__i_ (0 ≤ _s__i_ < 217)."},{"iden":"output","content":"Output the sum as described above, modulo 109 + 7"},{"iden":"examples","content":"Input\n\n2\n1 2\n\nOutput\n\n32\n\nInput\n\n3\n7 4 1\n\nOutput\n\n3520\n\nInput\n\n10\n1 3 0 7 3 7 6 5 7 5\n\nOutput\n\n1235424\n\nInput\n\n10\n50 9 11 44 39 40 5 39 23 7\n\nOutput\n\n113860062"}],"translated_statement":[{"iden":"statement","content":"给定一个包含 #cf_span[n] 个非负整数的数组 #cf_span[s]。\n\n一个整数五元组 #cf_span[(a, b, c, d, e)] 被称为有效的，当且仅当它满足以下条件：\n\n这里，'|' 表示按位或，'&' 表示按位与，'^' 表示按位异或运算。\n\n求所有有效五元组 #cf_span[(a, b, c, d, e)] 上 #cf_span[f(sa]|#cf_span[sb) * f(sc) * f(sd]^#cf_span[se)] 的和，其中 #cf_span[f(i)] 表示第 #cf_span[i] 个斐波那契数（#cf_span[f(0) = 0, f(1) = 1, f(i) = f(i - 1) + f(i - 2)]）。\n\n由于答案可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 106]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[si]（#cf_span[0 ≤ si < 217]）。\n\n请输出如上所述的和，对 #cf_span[109 + 7] 取模。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 106]）。第二行包含 #cf_span[n] 个整数 #cf_span[si]（#cf_span[0 ≤ si < 217]）。"},{"iden":"output","content":"请输出如上所述的和，对 #cf_span[109 + 7] 取模。"},{"iden":"examples","content":"输入\n2\n1 2\n输出\n32\n\n输入\n3\n7 4 1\n输出\n3520\n\n输入\n10\n1 3 0 7 3 7 6 5 7 5\n输出\n1235424\n\n输入\n10\n50 9 11 44 39 40 5 39 23 7\n输出\n113860062"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ s = [s_0, s_1, \\dots, s_{n-1}] $ be an array of $ n $ non-negative integers, with $ 0 \\leq s_i < 2^{17} $.\n\nLet $ f(i) $ denote the $ i $-th Fibonacci number, defined by:\n$$\nf(0) = 0, \\quad f(1) = 1, \\quad f(i) = f(i-1) + f(i-2) \\text{ for } i \\geq 2.\n$$\n\nA 5-tuple $ (a, b, c, d, e) \\in \\{0, 1, \\dots, n-1\\}^5 $ is **valid** if and only if:\n$$\n(s_a \\mid s_b) \\& (s_c \\oplus s_d) = s_e.\n$$\n\nDefine the sum:\n$$\n\\sum_{\\substack{(a,b,c,d,e) \\in [n]^5 \\\\ (s_a \\mid s_b) \\& (s_c \\oplus s_d) = s_e}} f(s_a \\mid s_b) \\cdot f(s_c) \\cdot f(s_d) \\cdot f(s_e) \\mod (10^9 + 7).\n$$\n\nCompute this sum modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}