Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define ld long double
- #define ull unsigned long long
- #define pb push_back
- #define pii pair<int, int>
- #define pll pair<ll, int>
- #define pld pair<ld, ll>
- #define fi first
- #define se second
- using namespace std;
- const int N = 2e5+5;
- const int M = 1e4+5;
- const ll mod = 1e9+7;
- const ll inf = 1e15;
- const ld base = 1e-6;
- int n, t, m, k, a[N], ans, lab[N], d[N], tong, l[N], r[N];
- vector<pii> adj[N];
- vector<int> vi;
- ll pw(ll k, ll n)
- {
- ll total = 1;
- for(; n; n >>= 1)
- {
- if(n&1)total = total * k % mod;
- k = k * k % mod;
- }
- return total;
- }
- void sol()
- {
- cin >> n;
- for(int i = 2; i < N; i ++)
- {
- if(!d[i])
- for(int j = i; j < N; j += i)d[j] = i;
- }
- for(int i = 1; i <= n; i ++)
- {
- cin >> a[i];
- while(a[i] > 1)
- {
- k = d[a[i]];
- m = 1;
- while(a[i] % k ==0)
- {
- m *= k;
- a[i] /= k;
- }
- adj[k].pb({i, m});
- }
- }
- ans = 1;
- for(int i = 2; i < N; i ++)
- {
- if(adj[i].empty())continue;
- vi.clear();
- m = adj[i].size();
- for(int j = 0; j < m; j ++)
- {
- while(!vi.empty() && adj[i][vi.back()].se <= adj[i][j].se)vi.pop_back();
- l[j] = vi.empty() ? 0 : adj[i][vi.back()].fi;
- vi.pb(j);
- }
- vi.clear();
- for(int j = m-1; j >= 0; j --)
- {
- while(!vi.empty() && adj[i][vi.back()].se < adj[i][j].se)vi.pop_back();
- r[j] = vi.empty() ? n+1 : adj[i][vi.back()].fi;
- ans = 1ll * pw(adj[i][j].se % mod, 1ll*(adj[i][j].fi-l[j]) * (r[j]-adj[i][j].fi) ) * ans % mod;
- vi.pb(j);
- }
- }
- cout << ans;
- }
- int main()
- {
- cin.tie(0);
- cout.tie(0);
- ios_base::sync_with_stdio(0);
- #define task "QUIZZ"
- if(fopen(task".inp", "r"))
- {
- freopen(task".inp", "r", stdin);
- freopen(task".out", "w", stdout);
- }
- int test = 1;
- //cin >> test;
- while(test -- > 0)sol();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement