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.