You are given an integer array \(A\) of length \(N\) and \(M\) queries. For each query, you are given three integers \(L, R, X\) and you should find the number of triplets \((i, j, k)\) such that \((L \leq i, j, k \leq R)\) and \((A_i \,\& \, A_j \,\&\, A_k = X)\).

Symbol \(\&\) denotes bitwise operator \(AND\).

Input format:

First line contains one integer \(N\) \((1 \leq N \leq 100000)\).

Next line contains \(N\) space-separated integers denoting the array \(A\) \((0 \leq A_i \leq 255)\).

The next line contains one integer \(M\) \((1 \leq M \leq 50000)\).

Next \(M\) lines contains three space-separated integers \(L, R, X\) \((1 \leq L \leq R \leq N, \,\,0 \leq X \leq 255)\)

Output format:

For each query, print the required answer modulo \(10^9+7\) in a new line.