title: Working of recursion in Exponential squaring?
body: <p>I was reading <strong>Exponential squaring method</strong> for fast multiplication from the codechef tutorial and i have <strong>few doubts related to this method</strong></p>
  
  <pre><code>long long int fast_exp(int base, int exp)
  {
  if(exp==1)
  return base;
  else
  {
      if(exp%2 == 0)
      {
          long long int base1 = pow(fast_exp(base, exp/2),2);
          if(base1 &gt;= 1000000007)
          return base1%1000000007;
          else
          return base1;
      }
      else
      {
          long long int ans = (base*  pow(fast_exp(base,(exp-1)/2),2));
          if(ans &gt;= 1000000007)
          return ans%1000000007;
          else
          return ans;
      }
    }
  } 
  </code></pre>
  
  <p><strong>My doubt is that</strong> does this method perform <strong>'%'</strong> operation at every recursive step or at the last after calculate actual <strong>base^exp</strong>.What i personally think that it calculates <strong>%</strong> at last step and also when i ran this code against </p>
  
  <pre><code>base=345 and exp=246;
  </code></pre>
  
  <p>it gave me <strong>garbage value</strong>.</p>
  
  <p><strong>I want to know that</strong>  When <strong>'%'</strong> operation is taking place,at everystep or just at the last step.</p>