- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- int qp(int a,int b){
- if(b==0)return 1;
- int T=qp(a,b>>1);T=T*T%mod;
- if(b&1)return T*a%mod;
- return T;
- }
- int calc(int n){
- int t=(0.5+sqrt(2.0*n));
- int res=(1-qp(2,t-2)*(t*t-3*t-2*n+4)%mod+mod)%mod;
- return res;
- }
- signed main(){
- int n;cin>>n;
- cout<<calc(n)<<endl;
- return 0;
- }