Given an array $A$ of $n$ integers. Let's denote function $f(l, r)$ as:
$$max(A_{l...r}) \oplus min(A_{l...r})$$
Calculate:
$$
\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r)
$$
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print the result, modulo $10^9+7$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
4
1 4 3 1
```
Output:
```
29
```