NENDS C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1000000000;
const ll N=1e5+5;
ll n,d,a[N],p[N],s,res;
long long lt(long long a,long long n)
{
    if(n==0) return 1;
    s=lt(a,n/2);
    s=(s*s)%mod;
    if(n%2==0)
    {
        return s;
    }
    else
    return s*(a%mod)%mod;
}
 
void solve()
{
    cin>>n;
    ll s = lt(2,n-2);
    cout << (((n+1)%mod)*(s%mod))%mod << endl;
 
}
int main()
{
    solve();
}