G. Sum the Fibonaccitime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array s of n non-negative integers.A 5-tuple of integers (a, b, c, d, e) is said to be valid if it satisfies the following conditions:   1 ≤ a, b, c, d, e ≤ n  (sa | sb) & sc & (sd ^ se) = 2i for some integer i  sa & sb = 0 Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.Find the sum of f(sa|sb) * f(sc) * f(sd^se) 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)).Since answer can be is huge output it modulo 109 + 7.InputThe first line of input contains an integer n (1 ≤ n ≤ 106).The second line of input contains n integers si (0 ≤ si < 217).OutputOutput the sum as described above, modulo 109 + 7ExamplesInput21 2Output32Input37 4 1Output3520Input101 3 0 7 3 7 6 5 7 5Output1235424Input1050 9 11 44 39 40 5 39 23 7Output113860062
Input21 2
Output32
['bitmasks', 'divide and conquer', 'dp', 'fft', 'math', '*2600']