fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const long double PI = 3.14159265359;
  7.  
  8. const int MOD = 1e9 + 7;
  9.  
  10. int modpower(int base, int exponent)
  11. {
  12. int res = 1;
  13. int b = base % MOD;
  14. while (exponent > 0)
  15. {
  16. if (exponent & 1 == 1)
  17. {
  18. res = (res * b) % MOD;
  19. }
  20. b = (b * b) % MOD;
  21. exponent >>= 1;
  22. }
  23. return res;
  24. }
  25.  
  26. void solve()
  27. {
  28. int n;
  29. cin >> n;
  30. vector<int> arr(n);
  31. map<int, int> freq;
  32. for (auto &val : arr)
  33. {
  34. cin >> val;
  35. freq[val]++;
  36. }
  37.  
  38. vector<int> dist;
  39. int mx = 0;
  40. for (auto [val, cnt] : freq)
  41. if (cnt == 1)
  42. dist.push_back(val);
  43. else
  44. mx = max(mx, val);
  45.  
  46. sort(dist.rbegin(), dist.rend());
  47. int ans = 1;
  48. for (int i = 0; i < dist.size(); i++)
  49. {
  50. if (dist[i] < mx)
  51. break;
  52. ans = (ans % MOD + modpower(dist[i] - 1, i + 1) % MOD) % MOD;
  53. }
  54. cout << ans % MOD << '\n';
  55. }
  56.  
  57. signed main(void)
  58. {
  59. ios_base::sync_with_stdio(0);
  60. cin.tie(0);
  61. cout.tie(0);
  62. if (fopen("input.txt", "r"))
  63. {
  64. freopen("input.txt", "r", stdin);
  65. freopen("output.txt", "w", stdout);
  66. }
  67. int t = 1;
  68. cin >> t;
  69. while (t--)
  70. {
  71. solve();
  72. }
  73. return 0;
  74. }
Success #stdin #stdout 0s 5344KB
stdin
5
3
2 2 1
2
1000000000 1
4
6 7 2 2
3
3 4 2
1
1
stdout
1
1000000000
32
9
1