title: Overflow while doing multiplication
body: <p>I want to calculate value of (N* N *(N+1)/2) mod M where this N can go upto 10^18 and M is at max up to 10^7. I tried to code it but don't know the reason that why it is overflowing. Here is my code : </p>
  
  <p>In main I do something like this :</p>
  
  <pre><code>long long tt=mulmod(N,N+1,MOD)*InverseEuler(2,MOD);
  long long mm=mulmod(tt,N,MOD);
  </code></pre>
  
  <p>And mulmod function find (A*B)%C . It is as follow :</p>
  
  <pre><code>long long mulmod(long long a,long long b,long long c)
  {    
      long long x = 0,y = a%c;
      while(b &gt; 0)
      {
          if(b%2 == 1)
          {
              x = (x+y)%c;
          }
          y = (y*2)%c;
          b /= 2;
      }
      return x%c;
  }
  </code></pre>
  
  <p>Also Inverse Euler is something like this :</p>
  
  <pre><code>long long p(long long n,int m,long long int MOD)
  {
      if(m == 0) return 1%MOD;
  
      long long x = p(n,m/2,MOD);
      if(m%2 == 0)
          return (x*x)%MOD;
      else
          return (((x*x)%MOD)*n)%MOD;
  }
  long long InverseEuler(int n,int MOD)
  {
      return p(n,MOD-2,MOD);
  }
  </code></pre>
  
  <p>Please help me in finding error in this code.</p>