#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template <size_t I, class H, class... T> struct TupleReaderWriter{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple_cat(tuple<H>(v),TupleReaderWriter<sizeof...(T)-1,T...>::r(i));}static void w(ostream&o,tuple<H,T...>&t,string d){TupleReaderWriter<I-1,H,T...>::w(o,t,d);o<<d<<get<I>(t);}};
template <class H, class... T> struct TupleReaderWriter<0,H,T...>{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple<H>(v);}static void w(ostream&o,tuple<H,T...>&t,string d){o<<get<0>(t);}};
template<class T>istream&operator>>(istream&i,vector<T>&v){for(auto&x:v)i>>x;return i;}
template<class T>ostream&operator<<(ostream&o,vector<T>&v){string delim="";for(auto&x:v)o<<delim<<x,delim=" ";return o;}
template <class... T> istream& operator>>(istream&i,tuple<T...>& t) { t = TupleReaderWriter<sizeof...(T), T...>::r(i); return i; }
template <class... T> ostream& operator<<(ostream& o, tuple<T...>& t) { string delim = " "; TupleReaderWriter<sizeof...(T) - 1, T...>::w(o, t, delim); return o; }
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using vector2d = vector<vector<T>>;
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }

/*!* [modint] *!*/
/*+* 剰余環整数 *+*/
struct int_m;
int_m invmod(int_m);
int_m powmod(int_m, i64);
struct int_m {
    static i64 m;
    i64 v;
    int_m() {}
    int_m(i64 x) : v(x) {}
    int_m operator+(const int_m &y) const { return (v + y.v) % m; }
    int_m operator-(const int_m &y) const { return (v - y.v + m) % m; }
    int_m operator*(const int_m &y) const { return (v * y.v) % m; }
    int_m operator/(const int_m &y) const { return *this * invmod(y); }
    int_m operator^(const i64   &y) const { return powmod(*this, y); }
    void operator+=(const int_m &y) { *this = *this + y; }
    void operator-=(const int_m &y) { *this = *this - y; }
    void operator*=(const int_m &y) { *this = *this * y; }
    void operator/=(const int_m &y) { *this = *this / y; }
    void operator^=(const i64   &y) { *this = *this ^ y; }
    bool operator==(const int_m &y) const { return v == y.v; }
    bool operator!=(const int_m &y) const { return v != y.v; }
    friend istream &operator>>(istream &ist, int_m m) { ist >> m.v; return ist; }
    friend ostream &operator<<(ostream &ost, int_m m) { ost << m.v; return ost; }
};
i64 int_m::m;
// O(log a)
int_m powmod(int_m a, i64 p) {
    int_m v = 1;
    for(int_m b = a; p > 0; p >>= 1, b *= b ) if(p & 1) v *= b;
    return v;
}
int_m invmod(int_m x) {
    return powmod(x, x.m - 2);
}

const i64 MOD = 1e9 + 7;

int main() {
    int_m::m = MOD;
    i64 N;
    cin >> N;
    vector<int_m> cur(3, 0), prev(3, 0);
    cur[0] = 1;
    for(int i = 63; i >= 0; i--) {
        swap(prev, cur);
        if(N & (1ll << i)) {
            cur[0] = prev[0];
            cur[1] = prev[0] + prev[1];
            cur[2] =           prev[1] * 2 + prev[2] * 3;
        } else {
            cur[0] = prev[0] + prev[1];
            cur[1] =           prev[1];
            cur[2] =           prev[1]     + prev[2] * 3;
        }
    }
    int_m ans = cur[0] + cur[1] + cur[2];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256