#include "secret.h"
#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
mt19937 mt(chrono::high_resolution_clock().now().time_since_epoch().count());
int randint(int l, int r) {
return mt() % (r - l + 1) + l;
}
const int N = 1005;
const int mod = 1e9 + 7;
int a[N][N], b[N];
int cnt = 0;
int binpow(int a, int b) {
int res = 1, cur = a;
while (b) {
if (b & 1)
res = 1ll * res * cur % mod;
cur = 1ll * cur * cur % mod, b >>= 1;
}
return res;
}
// int op(int a, int b) {
// return (a * 10ll + b) % mod;
// }
// int Secret(int a, int b) {
// cnt++;
// return op(a, b);
// }
void rec(int l, int r) {
if (l + 1 >= r)
return;
int m1 = l + r >> 1;
int m2 = m1 + 1;
for (int i = m1 - 1; i >= l; i--)
a[i][m1] = Secret(b[i], a[i + 1][m1]);
for (int i = m2 + 1; i <= r; i++)
a[m2][i] = Secret(a[m2][i - 1], b[i]);
rec(l, m1 - 1);
rec(m2 + 1, r);
}
int get(int tl, int tr, int l, int r) {
int m1 = l + r >> 1;
int m2 = m1 + 1;
if (tr < m1)
return get(tl, tr, l, m1 - 1);
if (m2 < tl)
return get(tl, tr, m2 + 1, r);
if (m1 == tr)
return a[tl][m1];
if (m2 == tl)
return a[m2][tr];
return Secret(a[tl][m1], a[m2][tr]);
}
int n;
void Init(int N, int A[]) {
n = N;
for (int i = 0; i < n; i++)
b[i] = A[i], a[i][i] = b[i];
rec(0, n - 1);
}
int Query(int l, int r) {
return get(l, r, 0, n - 1);
}
