fork download
  1. #include <bits/stdc++.h>
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. #define ll long long int
  6.  
  7. const ll mod = 1e9+7;
  8.  
  9.  
  10. ll mul(ll a,ll b){
  11. a%=mod;
  12. b%=mod;
  13. ll res = (a*b)%mod;
  14. return res;
  15. }
  16.  
  17. ll add(ll a,ll b){
  18. ll res = (a+b+mod)%mod;
  19. return res;
  20. }
  21.  
  22. ll binpow(ll a,ll b){
  23. ll res = 1;
  24. while(b>0){
  25. if(b&1)res = mul(res,a);
  26. a = mul(a,a);
  27. b>>=1;
  28. }
  29. return res;
  30. }
  31.  
  32.  
  33. ll inv(ll a){
  34. return binpow(a,mod-2);
  35. }
  36.  
  37. ll series(ll a,ll r,ll n){
  38. ll ans = mul(a,add(1,-binpow(r,n)));
  39. ans = mul(ans,inv(add(1,-r)));
  40. return ans%mod;
  41. }
  42.  
  43. int main(){
  44. ll n;
  45. cin>>n;
  46. // cout<<series(1,2,2);
  47. ll num = n;
  48. ll bi = 0;
  49. while(num!=0){
  50. num/=2;
  51. bi++;
  52. }
  53. ll p = 4;
  54. ll prev = 27;
  55. ll ans=0;
  56. for(int i = 3;i<=bi;i++){
  57. ll to=0,las;
  58. if(i==bi)to = n-p+1,las = n;
  59. else to = 2*p-p,las=2*p-1;
  60. ll aa = binpow(2,mul(to,i));
  61. // cout<<aa<<" "<<prev*aa<<" s\n";
  62. ans = mul(prev,aa);
  63. ll a = inv(binpow(2,i));
  64. ll r = a;
  65. ll fir = add(p,-mul(las,inv(binpow(2,mul(to,i)))));
  66. ll cur = 1;
  67. ll bb = mul(aa,inv(add(binpow(2,i),-1)));
  68. if(to>=1){
  69. cur = add(fir,series(a,r,to-1));
  70. cur = mul(cur,bb);
  71. }
  72. ans += (cur);
  73. ans%=mod;
  74. p*=2;
  75. prev=ans;
  76. }
  77. cout<<ans;
  78. return 0;
  79. }
  80.  
  81.  
Success #stdin #stdout 0s 5492KB
stdin
Standard input is empty
stdout
308459039