fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 1e9 + 7;
  4.  
  5. long long mypow(long long a, long long p){
  6. 	if(p == 0) return 1;
  7. 	if(p == 1) return (a % MOD);
  8. 	if(p & 1) return ((a % MOD) * (mypow(a, p - 1) % MOD)) % MOD;
  9. 	long long x = mypow(a, p / 2) % MOD;
  10. 	return (x * x) % MOD;
  11. }
  12.  
  13. long long inv(long long base){
  14. 	return mypow(base, MOD - 2);
  15. }
  16.  
  17. int main(){
  18. 	ios_base::sync_with_stdio(false);
  19. 	cin.tie(0);
  20. 	int n;
  21. 	cin >> n;
  22. 	vector<long long> a(n + 1);
  23. 	for(int i = 1; i <= n; i++) cin >> a[i];
  24. 	vector<long long> mult(n + 1);
  25. 	mult[0] = 1LL;
  26. 	vector<long long> mult1(n + 1);
  27. 	mult1[0] = 1LL;
  28. 	vector<int> z, z1;
  29. 	for(int i = 1; i <= n; i++){
  30. 		if(i & 1){
  31. 			if(a[i]) mult[i] = (1LL * mult[i - 1] * a[i]) % MOD;
  32. 			else{
  33. 				mult[i] = mult[i - 1];
  34. 				z.push_back(i);
  35. 			}
  36. 			mult1[i] = mult1[i - 1];
  37. 		}
  38. 		else{
  39. 			if(a[i]) mult1[i] = (1LL * mult1[i - 1] * a[i]) % MOD;
  40. 			else{
  41. 				mult1[i] = mult1[i - 1];
  42. 				z1.push_back(i);
  43. 			}
  44. 			mult[i] = mult[i - 1];
  45. 		}
  46. 	}
  47. 	int q;
  48. 	cin >> q;
  49. 	for(int i = 0; i < q; i++){
  50. 		int l, r;
  51. 		cin >> l >> r;
  52. 		if(l & 1){
  53. 			if(z.size()){
  54. 				int p = lower_bound(z.begin(), z.end(), l) - z.begin();
  55. 				if(z[p] <= r && z[p] >= l){
  56. 					cout << 0 << endl;
  57. 					continue;
  58. 				}
  59. 			}
  60. 			cout << (long long)(1LL * mult[r] * inv(mult[l - 1]) % MOD) << '\n';
  61. 		}
  62. 		else{
  63. 			if(z1.size()){
  64. 				int p = lower_bound(z1.begin(), z1.end(), l) - z1.begin();
  65. 				if(z1[p] <= r && z1[p] >= l){
  66. 					cout << 0 << endl;
  67. 					continue;
  68. 				}
  69. 			}
  70. 			cout << (long long)(1LL * mult1[r] * inv(mult1[l - 1]) % MOD) << '\n';
  71. 		}
  72. 	}
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
5
1 2 3 4 5
3
1 1
1 2
3 5
stdout
copy 
1
1
15
https://ideone.com/t7ReJL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!