对于Sn=(2^n-1+n)取模9973，
整数n（ 0 < n < = 1,000,000,000 ），

求各位大神帮忙！！

二分法 ，利用2^n=(2^(n/2))^2

可是当N很大时，Sn没取模就已经溢出了。

(a * b) % c = (a % c) * (b % c) % c

边计算边取模啊

超时的   才1秒
能给个具体代码吗？

int fun(int n)
{
  if (n < 30)  return (1 << n) % N;
  int ans = fun(n / 2);
  ans = ans * ans % N;
  if (n & 1)  ans = ans * 2 % N;
  return ans;
}