title: Modulus with negative numbers in C++
body: <p>I have been writing a program for the following recurrence relation:</p>
  
  <pre><code>An = 5An-1 - 2An-2  - An-3 + An-4
  </code></pre>
  
  <p>The output should be the Answer modulus 10^9 + 7..
  I wrote a brute force approach for this one as follows...</p>
  
  <pre><code>long long int t1=5, t2=9, t3=11, t4=13, sum;
  while(i--)
  {
      sum=((5*t4) - 2*t3 - t2 +t1)%MOD;
      t1=t2;
      t2=t3;
      t3=t4;
      t4=sum;
  }
  printf("%lld\n", sum);
  </code></pre>
  
  <p>where <code>MOD= 10^9 +7</code> 
  Every thing seems to be true.. but i am getting negative answer for some values.. and due to this problem, I am unable to find the correct solution... 
  Plz help about the right place to keep the <code>Modulus</code> </p>