title: Large values in segment tree for product range queries
body: <p>I wrote code for firing product range queries on an array.</p>
  
  <p>Note: This question not a duplicate to <a href="https://stackoverflow.com/questions/18029531/multiplication-in-a-range">Multiplication in a range</a>. My problem is something different</p>
  
  <p>I wrote the code for this,</p>
  
  <pre><code>// Program to show segment tree operations like construction, query and update
  #include &lt;stdio.h&gt;
  #include &lt;math.h&gt;
  #define R 1000000000
  
  typedef unsigned long long ull;
  int getMid(int s, int e) {  return s + (e -s)/2;  }
  
  ull getProdUtil(ull *st, int ss, int se, int qs, int qe, int index)
  {
      if (qs &lt;= ss &amp;&amp; qe &gt;= se)
          return st[index];
      if (se &lt; qs || ss &gt; qe)
          return 1;
      int mid = getMid(ss, se);
      return (getProdUtil(st, ss, mid, qs, qe, 2*index+1) %R *
             getProdUtil(st, mid+1, se, qs, qe, 2*index+2) % R )%R;
  }
  
  
  ull getProd(ull *st, int n, int qs, int qe)
  {
      if (qs &lt; 0 || qe &gt; n-1 || qs &gt; qe)
      {
          return 0;
      }
  
      return getProdUtil(st, 0, n-1, qs, qe, 0) % R;
  }
  
  
  ull constructSTUtil(ull arr[], int ss, int se, ull *st, int si)
  {
  
      if (ss == se)
      {
          st[si] = arr[ss];
          return arr[ss];
      }
  
      int mid = getMid(ss, se);
  
      ull l = (ull)constructSTUtil(arr, ss, mid, st, si*2+1)%R;
      ull r = (ull)constructSTUtil(arr, mid+1, se, st, si*2+2)%R;
      st[si] =  (l * r) % R;
      return st[si];
  }
  
  void init_array(ull *st, ull size){
      for(ull i=0;i&lt; size;i++){
          st[i] = 1;
      }
  }
  
  
  ull *constructST(ull arr[], int n)
  {
  
      int x = (int)(ceil(log2(n))); //Height of segment tree
      int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree
      ull *st = new ull[max_size];
      init_array(st, max_size);
      constructSTUtil(arr, 0, n-1, st, 0);
  
      return st;
  }
  
  void print_array(ull *array,int size){
      printf("\n");
      for(int i=0; i&lt; size;i++){
          printf("&lt;%d,%llu&gt; ", i+1,array[i]);
      }
  
  }
  
  int main()
  {
      int n;
      scanf("%d",&amp;n);
  
      ull arr[n];
  
      for(int i=0;i&lt;n;i++){
          scanf("%llu",&amp;arr[i]);
      }
  
      ull *st = constructST(arr, n);
  
      int t;
      scanf("%d", &amp;t);
  
      while(t--){
  
          int l,m,r;
          scanf("%d %d %d", &amp;l,&amp;r,&amp;m);
  
          ull result = getProd(st, n, l-1, r-1);
  
          printf("%lld\n",result % m);
  
          //int sizes = 100;
          //printf("%llu\n",st[0]);
          //print_array(st, sizes);
  
      }
  
      return 0;
  }
  
  
  The constraints are,
  1 ≤ N ≤ 100,000 (size of array)
  1 ≤ Ai ≤ 100 (array elements)
  1 ≤ T ≤ 100,000 (number of test cases)
  1 ≤ Li ≤ Ri ≤ N (Left and right ranges in query)
  1 ≤ Mi ≤ 10&lt;sup&gt;9&lt;/sup&gt; (Modulus for each test case. Each test case has to be modulu of this number)
  </code></pre>
  
  <p>Im pretty sure that R , that I have chosen is failing some test case. I tried R with 10<sup>18</sup> as well. But still same problem. Dont know why this is happening?</p>
  
  <p>My question is , is it the problem of R I have chosen or is it the problem of different M being passed in each test case. </p>
  
  <p><strong>Note: Truly not expecting a solution, just expecting a clue</strong></p>
  
  <p>Regards</p>