fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (1000000007U)
  5. void*wmem;
  6. char memarr[96000000];
  7. template<class S, class T> inline S min_L(S a,T b){
  8.   return a<=b?a:b;
  9. }
  10. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  11.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  12.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  13.   (*arr)=(T*)(*mem);
  14.   (*mem)=((*arr)+x);
  15. }
  16. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  17.   walloc1d(arr, x2-x1, mem);
  18.   (*arr) -= x1;
  19. }
  20. struct Modint{
  21.   unsigned val;
  22.   Modint(){
  23.     val=0;
  24.   }
  25.   Modint(int a){
  26.     val = ord(a);
  27.   }
  28.   Modint(unsigned a){
  29.     val = ord(a);
  30.   }
  31.   Modint(long long a){
  32.     val = ord(a);
  33.   }
  34.   Modint(unsigned long long a){
  35.     val = ord(a);
  36.   }
  37.   inline unsigned ord(unsigned a){
  38.     return a%MD;
  39.   }
  40.   inline unsigned ord(int a){
  41.     a %= (int)MD;
  42.     if(a < 0){
  43.       a += MD;
  44.     }
  45.     return a;
  46.   }
  47.   inline unsigned ord(unsigned long long a){
  48.     return a%MD;
  49.   }
  50.   inline unsigned ord(long long a){
  51.     a %= (int)MD;
  52.     if(a < 0){
  53.       a += MD;
  54.     }
  55.     return a;
  56.   }
  57.   inline unsigned get(){
  58.     return val;
  59.   }
  60.   inline Modint &operator+=(Modint a){
  61.     val += a.val;
  62.     if(val >= MD){
  63.       val -= MD;
  64.     }
  65.     return *this;
  66.   }
  67.   inline Modint &operator-=(Modint a){
  68.     if(val < a.val){
  69.       val = val + MD - a.val;
  70.     }
  71.     else{
  72.       val -= a.val;
  73.     }
  74.     return *this;
  75.   }
  76.   inline Modint &operator*=(Modint a){
  77.     val = ((unsigned long long)val*a.val)%MD;
  78.     return *this;
  79.   }
  80.   inline Modint &operator/=(Modint a){
  81.     return *this *= a.inverse();
  82.   }
  83.   inline Modint operator+(Modint a){
  84.     return Modint(*this)+=a;
  85.   }
  86.   inline Modint operator-(Modint a){
  87.     return Modint(*this)-=a;
  88.   }
  89.   inline Modint operator*(Modint a){
  90.     return Modint(*this)*=a;
  91.   }
  92.   inline Modint operator/(Modint a){
  93.     return Modint(*this)/=a;
  94.   }
  95.   inline Modint operator+(int a){
  96.     return Modint(*this)+=Modint(a);
  97.   }
  98.   inline Modint operator-(int a){
  99.     return Modint(*this)-=Modint(a);
  100.   }
  101.   inline Modint operator*(int a){
  102.     return Modint(*this)*=Modint(a);
  103.   }
  104.   inline Modint operator/(int a){
  105.     return Modint(*this)/=Modint(a);
  106.   }
  107.   inline Modint operator+(long long a){
  108.     return Modint(*this)+=Modint(a);
  109.   }
  110.   inline Modint operator-(long long a){
  111.     return Modint(*this)-=Modint(a);
  112.   }
  113.   inline Modint operator*(long long a){
  114.     return Modint(*this)*=Modint(a);
  115.   }
  116.   inline Modint operator/(long long a){
  117.     return Modint(*this)/=Modint(a);
  118.   }
  119.   inline Modint operator-(void){
  120.     Modint res;
  121.     if(val){
  122.       res.val=MD-val;
  123.     }
  124.     else{
  125.       res.val=0;
  126.     }
  127.     return res;
  128.   }
  129.   inline operator bool(void){
  130.     return val!=0;
  131.   }
  132.   inline operator int(void){
  133.     return get();
  134.   }
  135.   inline operator long long(void){
  136.     return get();
  137.   }
  138.   inline Modint inverse(){
  139.     int a = val;
  140.     int b = MD;
  141.     int u = 1;
  142.     int v = 0;
  143.     int t;
  144.     Modint res;
  145.     while(b){
  146.       t = a / b;
  147.       a -= t * b;
  148.       swap(a, b);
  149.       u -= t * v;
  150.       swap(u, v);
  151.     }
  152.     if(u < 0){
  153.       u += MD;
  154.     }
  155.     res.val = u;
  156.     return res;
  157.   }
  158.   inline Modint pw(unsigned long long b){
  159.     Modint a(*this);
  160.     Modint res;
  161.     res.val = 1;
  162.     while(b){
  163.       if(b&1){
  164.         res *= a;
  165.       }
  166.       b >>= 1;
  167.       a *= a;
  168.     }
  169.     return res;
  170.   }
  171.   inline bool operator==(int a){
  172.     return ord(a)==val;
  173.   }
  174.   inline bool operator!=(int a){
  175.     return ord(a)!=val;
  176.   }
  177. }
  178. ;
  179. inline Modint operator+(int a, Modint b){
  180.   return Modint(a)+=b;
  181. }
  182. inline Modint operator-(int a, Modint b){
  183.   return Modint(a)-=b;
  184. }
  185. inline Modint operator*(int a, Modint b){
  186.   return Modint(a)*=b;
  187. }
  188. inline Modint operator/(int a, Modint b){
  189.   return Modint(a)/=b;
  190. }
  191. inline Modint operator+(long long a, Modint b){
  192.   return Modint(a)+=b;
  193. }
  194. inline Modint operator-(long long a, Modint b){
  195.   return Modint(a)-=b;
  196. }
  197. inline Modint operator*(long long a, Modint b){
  198.   return Modint(a)*=b;
  199. }
  200. inline Modint operator/(long long a, Modint b){
  201.   return Modint(a)/=b;
  202. }
  203. inline int my_getchar_unlocked(){
  204.   static char buf[1048576];
  205.   static int s = 1048576;
  206.   static int e = 1048576;
  207.   if(s == e && e == 1048576){
  208.     e = fread_unlocked(buf, 1, 1048576, stdin);
  209.     s = 0;
  210.   }
  211.   if(s == e){
  212.     return EOF;
  213.   }
  214.   return buf[s++];
  215. }
  216. inline void rd(int &x){
  217.   int k;
  218.   int m=0;
  219.   x=0;
  220.   for(;;){
  221.     k = my_getchar_unlocked();
  222.     if(k=='-'){
  223.       m=1;
  224.       break;
  225.     }
  226.     if('0'<=k&&k<='9'){
  227.       x=k-'0';
  228.       break;
  229.     }
  230.   }
  231.   for(;;){
  232.     k = my_getchar_unlocked();
  233.     if(k<'0'||k>'9'){
  234.       break;
  235.     }
  236.     x=x*10+k-'0';
  237.   }
  238.   if(m){
  239.     x=-x;
  240.   }
  241. }
  242. struct MY_WRITER{
  243.   char buf[1048576];
  244.   int s;
  245.   int e;
  246.   MY_WRITER(){
  247.     s = 0;
  248.     e = 1048576;
  249.   }
  250.   ~MY_WRITER(){
  251.     if(s){
  252.       fwrite_unlocked(buf, 1, s, stdout);
  253.     }
  254.   }
  255. }
  256. ;
  257. MY_WRITER MY_WRITER_VAR;
  258. void my_putchar_unlocked(int a){
  259.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  260.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  261.     MY_WRITER_VAR.s = 0;
  262.   }
  263.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  264. }
  265. inline void wt_L(char a){
  266.   my_putchar_unlocked(a);
  267. }
  268. inline void wt_L(int x){
  269.   int s=0;
  270.   int m=0;
  271.   char f[10];
  272.   if(x<0){
  273.     m=1;
  274.     x=-x;
  275.   }
  276.   while(x){
  277.     f[s++]=x%10;
  278.     x/=10;
  279.   }
  280.   if(!s){
  281.     f[s++]=0;
  282.   }
  283.   if(m){
  284.     my_putchar_unlocked('-');
  285.   }
  286.   while(s--){
  287.     my_putchar_unlocked(f[s]+'0');
  288.   }
  289. }
  290. inline void wt_L(Modint x){
  291.   int i;
  292.   i = (int)x;
  293.   wt_L(i);
  294. }
  295. int Prime_L(int N, int res[], void *mem=wmem){
  296.   int i;
  297.   int a;
  298.   int b;
  299.   int sz = 1;
  300.   const int r = 23000;
  301.   bool*isprime;
  302.   int*sf;
  303.   int ss = 1;
  304.   walloc1d(&isprime, r, &mem);
  305.   walloc1d(&sf, r, &mem);
  306.   isprime = (bool*)mem;
  307.   sf = (int*)(isprime + r);
  308.   N /= 2;
  309.   res[0] = 2;
  310.   b =min_L(r, N);
  311.   for(i=(1);i<(b);i++){
  312.     isprime[i] = 1;
  313.   }
  314.   for(i=(1);i<(b);i++){
  315.     if(isprime[i]){
  316.       res[sz++] = 2*i+1;
  317.       sf[ss] = 2*i*(i+1);
  318.       if(sf[ss] < N){
  319.         while(sf[ss] < r){
  320.           isprime[sf[ss]] = 0;
  321.           sf[ss] += res[ss];
  322.         }
  323.         ss++;
  324.       }
  325.     }
  326.   }
  327.   for(a=r; a<N; a+=r){
  328.     b =min_L(a + r, N);
  329.     isprime -= r;
  330.     for(i=(a);i<(b);i++){
  331.       isprime[i] = 1;
  332.     }
  333.     for(i=(1);i<(ss);i++){
  334.       while(sf[i] < b){
  335.         isprime[sf[i]] = 0;
  336.         sf[i] += res[i];
  337.       }
  338.     }
  339.     for(i=(a);i<(b);i++){
  340.       if(isprime[i]){
  341.         res[sz++] = 2*i+1;
  342.       }
  343.     }
  344.   }
  345.   return sz;
  346. }
  347. template<class T, class S> inline T pow_L(T a, S b){
  348.   T res = 1;
  349.   res = 1;
  350.   for(;;){
  351.     if(b&1){
  352.       res *= a;
  353.     }
  354.     b >>= 1;
  355.     if(b==0){
  356.       break;
  357.     }
  358.     a *= a;
  359.   }
  360.   return res;
  361. }
  362. inline double pow_L(double a, double b){
  363.   return pow(a,b);
  364. }
  365. template<class T> struct Arr1d{
  366.   int n;
  367.   int mem;
  368.   T*d;
  369.   T& operator[](int a){
  370.     return d[a];
  371.   }
  372.   void sort(){
  373.     reset();
  374.     std::sort(d, d+n);
  375.   }
  376.   int set_cumulative_sum;
  377.   int cumulative_sum_mem;
  378.   T*cumulative_sum;
  379.   void setSum(void){
  380.     int i;
  381.     set_cumulative_sum = 1;
  382.     if(cumulative_sum_mem < n+1){
  383.       delete[] cumulative_sum;
  384.       cumulative_sum = new T[n+1];
  385.       cumulative_sum_mem = n+1;
  386.     }
  387.     cumulative_sum[0] = 0;
  388.     for(i=(0);i<(n);i++){
  389.       cumulative_sum[i+1] = cumulative_sum[i] + d[i];
  390.     }
  391.   }
  392.   T getSum(int i, int j){
  393.     if(set_cumulative_sum==0){
  394.       setSum();
  395.     }
  396.     return cumulative_sum[j+1] - cumulative_sum[i];
  397.   }
  398.   int set_const_len_left;
  399.   int const_len_left_mem;
  400.   int*const_len_left;
  401.   void setConstLenLeft(void){
  402.     int i;
  403.     set_const_len_left = 1;
  404.     if(const_len_left_mem < n){
  405.       delete[] const_len_left;
  406.       const_len_left = new int[n];
  407.       const_len_left_mem = n;
  408.     }
  409.     for(i=(0);i<(n);i++){
  410.       const_len_left[i] = 1;
  411.     }
  412.     for(i=(1);i<(n);i++){
  413.       if(d[i]==d[i-1]){
  414.         const_len_left[i] = const_len_left[i-1] + 1;
  415.       }
  416.     }
  417.   }
  418.   int ConstLenLeft(int st, T val){
  419.     if(!set_const_len_left){
  420.       setConstLenLeft();
  421.     }
  422.     if(val != d[st]){
  423.       return 0;
  424.     }
  425.     return const_len_left[st];
  426.   }
  427.   int ConstLenLeft(int st){
  428.     if(!set_const_len_left){
  429.       setConstLenLeft();
  430.     }
  431.     return const_len_left[st];
  432.   }
  433.   int ConstLenLeftCyclic(int st, T val){
  434.     if(!set_const_len_left){
  435.       setConstLenLeft();
  436.     }
  437.     st %= n;
  438.     if(st < 0){
  439.       st += n;
  440.     }
  441.     if(val != d[st]){
  442.       return 0;
  443.     }
  444.     if(const_len_left[st] != st+1 || d[st] != d[n-1]){
  445.       return const_len_left[st];
  446.     }
  447.     if(const_len_left[n-1] == n){
  448.       return 1073709056;
  449.     }
  450.     return const_len_left[st] + const_len_left[n-1];
  451.   }
  452.   int ConstLenLeftCyclic(int st){
  453.     if(!set_const_len_left){
  454.       setConstLenLeft();
  455.     }
  456.     st %= n;
  457.     if(st < 0){
  458.       st += n;
  459.     }
  460.     if(const_len_left[st] != st+1 || d[st] != d[n-1]){
  461.       return const_len_left[st];
  462.     }
  463.     if(const_len_left[n-1] == n){
  464.       return 1073709056;
  465.     }
  466.     return const_len_left[st] + const_len_left[n-1];
  467.   }
  468.   int set_const_len_right;
  469.   int const_len_right_mem;
  470.   int*const_len_right;
  471.   void setConstLenRight(void){
  472.     int i;
  473.     set_const_len_right = 1;
  474.     if(const_len_right_mem < n){
  475.       delete[] const_len_right;
  476.       const_len_right = new int[n];
  477.       const_len_right_mem = n;
  478.     }
  479.     for(i=(0);i<(n);i++){
  480.       const_len_right[i] = 1;
  481.     }
  482.     for(i=(n-1)-1;i>=(0);i--){
  483.       if(d[i]==d[i+1]){
  484.         const_len_right[i] = const_len_right[i+1] + 1;
  485.       }
  486.     }
  487.   }
  488.   int ConstLenRight(int st, T val){
  489.     if(!set_const_len_right){
  490.       setConstLenRight();
  491.     }
  492.     if(val != d[st]){
  493.       return 0;
  494.     }
  495.     return const_len_right[st];
  496.   }
  497.   int ConstLenRight(int st){
  498.     if(!set_const_len_right){
  499.       setConstLenRight();
  500.     }
  501.     return const_len_right[st];
  502.   }
  503.   int ConstLenRightCyclic(int st, T val){
  504.     if(!set_const_len_right){
  505.       setConstLenRight();
  506.     }
  507.     if(val != d[st]){
  508.       return 0;
  509.     }
  510.     st %= n;
  511.     if(st < 0){
  512.       st += n;
  513.     }
  514.     if(const_len_right[st] != n-st || d[st] != d[0]){
  515.       return const_len_right[st];
  516.     }
  517.     if(const_len_right[0] == n){
  518.       return 1073709056;
  519.     }
  520.     return const_len_right[st] + const_len_right[0];
  521.   }
  522.   int ConstLenRightCyclic(int st){
  523.     if(!set_const_len_right){
  524.       setConstLenRight();
  525.     }
  526.     st %= n;
  527.     if(st < 0){
  528.       st += n;
  529.     }
  530.     if(const_len_right[st] != n-st || d[st] != d[0]){
  531.       return const_len_right[st];
  532.     }
  533.     if(const_len_right[0] == n){
  534.       return 1073709056;
  535.     }
  536.     return const_len_right[st] + const_len_right[0];
  537.   }
  538.   int set_dhist;
  539.   int dhist_mem;
  540.   int*dhist;
  541.   T dhist_mn;
  542.   T dhist_mx;
  543.   void setDHist(void){
  544.     int i;
  545.     int len;
  546.     set_dhist = 1;
  547.     if(n==0){
  548.       return;
  549.     }
  550.     dhist_mn = dhist_mx = d[0];
  551.     for(i=(1);i<(n);i++){
  552.       if(dhist_mn > d[i]){
  553.         dhist_mn = d[i];
  554.       }
  555.       if(dhist_mx < d[i]){
  556.         dhist_mx = d[i];
  557.       }
  558.     }
  559.     len = dhist_mx - dhist_mn + 1;
  560.     if(dhist_mem < len){
  561.       delete[] dhist;
  562.       dhist = new int[len];
  563.       dhist_mem = len;
  564.     }
  565.     for(i=(0);i<(len);i++){
  566.       dhist[i] = 0;
  567.     }
  568.     for(i=(0);i<(n);i++){
  569.       dhist[d[i] - dhist_mn]++;
  570.     }
  571.   }
  572.   int dHist(T x){
  573.     if(set_dhist==0){
  574.       setDHist();
  575.     }
  576.     if(n == 0 || x < dhist_mn || x > dhist_mx){
  577.       return 0;
  578.     }
  579.     return dhist[x - dhist_mn];
  580.   }
  581.   int set_prevLE;
  582.   int prevLE_mem;
  583.   int*prevLE;
  584.   int setPrevLE(void *mem = wmem){
  585.     int i;
  586.     int s = 0;
  587.     int*st;
  588.     set_prevLE = 1;
  589.     if(prevLE_mem < n){
  590.       delete[] prevLE;
  591.       prevLE = new int[n];
  592.       prevLE_mem = n;
  593.     }
  594.     walloc1d(&st, n, &mem);
  595.     for(i=(0);i<(n);i++){
  596.       while(s && d[st[s-1]] > d[i]){
  597.         s--;
  598.       }
  599.       if(s==0){
  600.         prevLE[i] = -1;
  601.       }
  602.       else{
  603.         prevLE[i] = st[s-1];
  604.       }
  605.       st[s++] = i;
  606.     }
  607.   }
  608.   int PrevLE(int i){
  609.     if(set_prevLE==0){
  610.       setPrevLE();
  611.     }
  612.     return prevLE[i];
  613.   }
  614.   int set_prevLT;
  615.   int prevLT_mem;
  616.   int*prevLT;
  617.   int setPrevLT(void *mem = wmem){
  618.     int i;
  619.     int s = 0;
  620.     int*st;
  621.     set_prevLT = 1;
  622.     if(prevLT_mem < n){
  623.       delete[] prevLT;
  624.       prevLT = new int[n];
  625.       prevLT_mem = n;
  626.     }
  627.     walloc1d(&st, n, &mem);
  628.     for(i=(0);i<(n);i++){
  629.       while(s && d[st[s-1]] >= d[i]){
  630.         s--;
  631.       }
  632.       if(s==0){
  633.         prevLT[i] = -1;
  634.       }
  635.       else{
  636.         prevLT[i] = st[s-1];
  637.       }
  638.       st[s++] = i;
  639.     }
  640.   }
  641.   int PrevLT(int i){
  642.     if(set_prevLT==0){
  643.       setPrevLT();
  644.     }
  645.     return prevLT[i];
  646.   }
  647.   int set_prevGE;
  648.   int prevGE_mem;
  649.   int*prevGE;
  650.   int setPrevGE(void *mem = wmem){
  651.     int i;
  652.     int s = 0;
  653.     int*st;
  654.     set_prevGE = 1;
  655.     if(prevGE_mem < n){
  656.       delete[] prevGE;
  657.       prevGE = new int[n];
  658.       prevGE_mem = n;
  659.     }
  660.     walloc1d(&st, n, &mem);
  661.     for(i=(0);i<(n);i++){
  662.       while(s && d[st[s-1]] < d[i]){
  663.         s--;
  664.       }
  665.       if(s==0){
  666.         prevGE[i] = -1;
  667.       }
  668.       else{
  669.         prevGE[i] = st[s-1];
  670.       }
  671.       st[s++] = i;
  672.     }
  673.   }
  674.   int PrevGE(int i){
  675.     if(set_prevGE==0){
  676.       setPrevGE();
  677.     }
  678.     return prevGE[i];
  679.   }
  680.   int set_prevGT;
  681.   int prevGT_mem;
  682.   int*prevGT;
  683.   int setPrevGT(void *mem = wmem){
  684.     int i;
  685.     int s = 0;
  686.     int*st;
  687.     set_prevGT = 1;
  688.     if(prevGT_mem < n){
  689.       delete[] prevGT;
  690.       prevGT = new int[n];
  691.       prevGT_mem = n;
  692.     }
  693.     walloc1d(&st, n, &mem);
  694.     for(i=(0);i<(n);i++){
  695.       while(s && d[st[s-1]] <= d[i]){
  696.         s--;
  697.       }
  698.       if(s==0){
  699.         prevGT[i] = -1;
  700.       }
  701.       else{
  702.         prevGT[i] = st[s-1];
  703.       }
  704.       st[s++] = i;
  705.     }
  706.   }
  707.   int PrevGT(int i){
  708.     if(set_prevGT==0){
  709.       setPrevGT();
  710.     }
  711.     return prevGT[i];
  712.   }
  713.   int set_nextLE;
  714.   int nextLE_mem;
  715.   int*nextLE;
  716.   int setNextLE(void *mem = wmem){
  717.     int i;
  718.     int s = 0;
  719.     int*st;
  720.     set_nextLE = 1;
  721.     if(nextLE_mem < n){
  722.       delete[] nextLE;
  723.       nextLE = new int[n];
  724.       nextLE_mem = n;
  725.     }
  726.     walloc1d(&st, n, &mem);
  727.     for(i=(n)-1;i>=(0);i--){
  728.       while(s && d[st[s-1]] > d[i]){
  729.         s--;
  730.       }
  731.       if(s==0){
  732.         nextLE[i] = n;
  733.       }
  734.       else{
  735.         nextLE[i] = st[s-1];
  736.       }
  737.       st[s++] = i;
  738.     }
  739.   }
  740.   int NextLE(int i){
  741.     if(set_nextLE==0){
  742.       setNextLE();
  743.     }
  744.     return nextLE[i];
  745.   }
  746.   int set_nextLT;
  747.   int nextLT_mem;
  748.   int*nextLT;
  749.   int setNextLT(void *mem = wmem){
  750.     int i;
  751.     int s = 0;
  752.     int*st;
  753.     set_nextLT = 1;
  754.     if(nextLT_mem < n){
  755.       delete[] nextLT;
  756.       nextLT = new int[n];
  757.       nextLT_mem = n;
  758.     }
  759.     walloc1d(&st, n, &mem);
  760.     for(i=(n)-1;i>=(0);i--){
  761.       while(s && d[st[s-1]] >= d[i]){
  762.         s--;
  763.       }
  764.       if(s==0){
  765.         nextLT[i] = n;
  766.       }
  767.       else{
  768.         nextLT[i] = st[s-1];
  769.       }
  770.       st[s++] = i;
  771.     }
  772.   }
  773.   int NextLT(int i){
  774.     if(set_nextLT==0){
  775.       setNextLT();
  776.     }
  777.     return nextLT[i];
  778.   }
  779.   int set_nextGE;
  780.   int nextGE_mem;
  781.   int*nextGE;
  782.   int setNextGE(void *mem = wmem){
  783.     int i;
  784.     int s = 0;
  785.     int*st;
  786.     set_nextGE = 1;
  787.     if(nextGE_mem < n){
  788.       delete[] nextGE;
  789.       nextGE = new int[n];
  790.       nextGE_mem = n;
  791.     }
  792.     walloc1d(&st, n, &mem);
  793.     for(i=(n)-1;i>=(0);i--){
  794.       while(s && d[st[s-1]] < d[i]){
  795.         s--;
  796.       }
  797.       if(s==0){
  798.         nextGE[i] = n;
  799.       }
  800.       else{
  801.         nextGE[i] = st[s-1];
  802.       }
  803.       st[s++] = i;
  804.     }
  805.   }
  806.   int NextGE(int i){
  807.     if(set_nextGE==0){
  808.       setNextGE();
  809.     }
  810.     return nextGE[i];
  811.   }
  812.   int set_nextGT;
  813.   int nextGT_mem;
  814.   int*nextGT;
  815.   int setNextGT(void *mem = wmem){
  816.     int i;
  817.     int s = 0;
  818.     int*st;
  819.     set_nextGT = 1;
  820.     if(nextGT_mem < n){
  821.       delete[] nextGT;
  822.       nextGT = new int[n];
  823.       nextGT_mem = n;
  824.     }
  825.     walloc1d(&st, n, &mem);
  826.     for(i=(n)-1;i>=(0);i--){
  827.       while(s && d[st[s-1]] <= d[i]){
  828.         s--;
  829.       }
  830.       if(s==0){
  831.         nextGT[i] = n;
  832.       }
  833.       else{
  834.         nextGT[i] = st[s-1];
  835.       }
  836.       st[s++] = i;
  837.     }
  838.   }
  839.   int NextGT(int i){
  840.     if(set_nextGT==0){
  841.       setNextGT();
  842.     }
  843.     return nextGT[i];
  844.   }
  845.   void reset(){
  846.     set_cumulative_sum = 0;
  847.     set_const_len_left = 0;
  848.     set_const_len_right = 0;
  849.     set_dhist = 0;
  850.     set_prevLE = set_prevLT = set_prevGE = set_prevGT = 0;
  851.     set_nextLE = set_nextLT = set_nextGE = set_nextGT = 0;
  852.   }
  853.   void memory_expand(int nn){
  854.     if(mem < nn){
  855.       delete[] d;
  856.       d = new T[nn];
  857.       mem = nn;
  858.     }
  859.   }
  860.   void malloc(int nn){
  861.     reset();
  862.     memory_expand(nn);
  863.     n = nn;
  864.   }
  865.   void setN(int nn){
  866.     reset();
  867.     memory_expand(nn);
  868.     n = nn;
  869.   }
  870.   void set(vector<T> &a){
  871.     int i;
  872.     int nn = a.size();
  873.     setN(nn);
  874.     for(i=(0);i<(nn);i++){
  875.       d[i] = a[i];
  876.     }
  877.   }
  878.   void set(int nn, T a[]){
  879.     int i;
  880.     setN(nn);
  881.     for(i=(0);i<(nn);i++){
  882.       d[i] = a[i];
  883.     }
  884.   }
  885.   void free(){
  886.     destructor();
  887.   }
  888.   void constructor(){
  889.     n = mem = 0;
  890.     d = NULL;
  891.     set_cumulative_sum = 0;
  892.     cumulative_sum_mem = 0;
  893.     cumulative_sum = NULL;
  894.     set_const_len_left = 0;
  895.     const_len_left_mem = 0;
  896.     const_len_left = NULL;
  897.     set_const_len_right = 0;
  898.     const_len_right_mem = 0;
  899.     const_len_right = NULL;
  900.     set_dhist = 0;
  901.     dhist_mem = 0;
  902.     dhist = NULL;
  903.     set_prevLE = set_prevLT = set_prevGE = set_prevGT = 0;
  904.     prevLE_mem = prevLT_mem = prevGE_mem = prevGT_mem = 0;
  905.     prevLE = prevLT = prevGE = prevGT = NULL;
  906.     set_nextLE = set_nextLT = set_nextGE = set_nextGT = 0;
  907.     nextLE_mem = nextLT_mem = nextGE_mem = nextGT_mem = 0;
  908.     nextLE = nextLT = nextGE = nextGT = NULL;
  909.   }
  910.   void constructor(int nn){
  911.     constructor();
  912.     malloc(nn);
  913.   }
  914.   void destructor(){
  915.     delete[] d;
  916.     d = NULL;
  917.     mem = n = 0;
  918.     set_cumulative_sum = 0;
  919.     cumulative_sum_mem = 0;
  920.     delete[] cumulative_sum;
  921.     cumulative_sum = NULL;
  922.     set_const_len_left = 0;
  923.     const_len_left_mem = 0;
  924.     delete[] const_len_left;
  925.     const_len_left = NULL;
  926.     set_const_len_right = 0;
  927.     const_len_right_mem = 0;
  928.     delete[] const_len_right;
  929.     const_len_right = NULL;
  930.     set_dhist = 0;
  931.     dhist_mem = 0;
  932.     delete[] dhist;
  933.     dhist = NULL;
  934.   }
  935.   Arr1d(){
  936.     constructor();
  937.   }
  938.   Arr1d(int nn){
  939.     constructor(nn);
  940.   }
  941.   ~Arr1d(){
  942.     destructor();
  943.   }
  944. }
  945. ;
  946. int N;
  947. Arr1d<int> A;
  948. Arr1d<int> arr;
  949. int ps;
  950. int p[320];
  951. vector<int> ind[100000+1];
  952. int main(){
  953.   int i, m;
  954.   wmem = memarr;
  955.   Modint res = 1;
  956.   long long r;
  957.   long long t;
  958.   rd(N);
  959.   A.malloc(N);
  960.   {
  961.     int Lj4PdHRW;
  962.     for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
  963.       rd(A[Lj4PdHRW]);
  964.     }
  965.   }
  966.   ps =Prime_L(320, p);
  967.   for(m=(0);m<(ps);m++){
  968.     int i;
  969.     arr.setN(N);
  970.     for(i=(0);i<(N);i++){
  971.       arr[i] = 0;
  972.     }
  973.     for(i=(0);i<(N);i++){
  974.       arr[i] = 0;
  975.       while(A[i] % p[m] == 0){
  976.         A[i] /= p[m];
  977.         arr[i]++;
  978.       }
  979.     }
  980.     r = 0;
  981.     for(i=(0);i<(N);i++){
  982.       r += (long long)(i - arr.PrevGE(i)) * (arr.NextGT(i) - i) * arr[i];
  983.     }
  984.     res *=(pow_L(Modint(p[m]),r));
  985.   }
  986.   for(m=(0);m<(100000+1);m++){
  987.     ind[m].push_back(-1);
  988.   }
  989.   for(i=(0);i<(N);i++){
  990.     if(A[i] > 1){
  991.       ind[A[i]].push_back(i);
  992.     }
  993.   }
  994.   for(m=(0);m<(100000+1);m++){
  995.     ind[m].push_back(N);
  996.   }
  997.   for(m=(0);m<(100000+1);m++){
  998.     if(ind[m].size() > 2){
  999.       r = (long long) N * (N+1) / 2;
  1000.       for(i=(1);i<(ind[m].size());i++){
  1001.         long long t = ind[m][i] - ind[m][i-1];
  1002.         r -= t * (t-1) / 2;
  1003.       }
  1004.       res *=(pow_L(Modint(m),r));
  1005.     }
  1006.   }
  1007.   wt_L(res);
  1008.   wt_L('\n');
  1009.   return 0;
  1010. }
  1011. // cLay version 20201123-1
  1012.  
  1013. // --- original code ---
  1014. // int N;
  1015. // Arr1d<int> A, arr;
  1016. // int ps, p[320];
  1017. // vector<int> ind[1d5+1];
  1018. // {
  1019. //   Modint res = 1;
  1020. //   ll r, t;
  1021. //   rd(N,A(N));
  1022. //   ps = Prime(320, p);
  1023. // 
  1024. //   rep(m,ps){
  1025. //     arr.setN(N);
  1026. //     rep(i,N) arr[i] = 0;
  1027. //     rep(i,N){
  1028. //       arr[i] = 0;
  1029. //       while(A[i] % p[m] == 0) A[i] /= p[m], arr[i]++;
  1030. //     }
  1031. //     r = 0;
  1032. //     rep(i,N) r += (ll)(i - arr.PrevGE(i)) * (arr.NextGT(i) - i) * arr[i];
  1033. //     res *= Modint(p[m]) ** r;
  1034. //   }
  1035. // 
  1036. //   rep(m,1d5+1) ind[m].push_back(-1);
  1037. //   rep(i,N) if(A[i] > 1) ind[A[i]].push_back(i);
  1038. //   rep(m,1d5+1) ind[m].push_back(N);
  1039. //   rep(m,1d5+1) if(ind[m].size() > 2){
  1040. //     r = (ll) N * (N+1) / 2;
  1041. //     rep(i,1,ind[m].size()){
  1042. //       ll t = ind[m][i] - ind[m][i-1];
  1043. //       r -= t * (t-1) / 2;
  1044. //     }
  1045. //     res *= Modint(m) ** r;
  1046. //   }
  1047. // 
  1048. //   wt(res);
  1049. // }
  1050.  
Time limit exceeded #stdin #stdout 5s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T7BSFR
language:
C++ (gcc 8.3)
created:
3 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!