#include <stdio.h>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define long long long
const long M = 1000000007; // modulo
map<long, long> F;
vector<long> T[1234];
long f(long n, int Depth) {
T[Depth].push_back(n);
if (F.count(n)) return F[n];
long k=n/2;
if (n%2==0) { // n=2*k
return F[n] = (f(k, Depth+1)*f(k, Depth+1) + f(k-1, Depth+1)*f(k-1, Depth+1)) % M;
} else { // n=2*k+1
return F[n] = (f(k, Depth+1)*f(k+1, Depth+1) + f(k-1, Depth+1)*f(k, Depth+1)) % M;
}
}
main(){
long n;
F[0]=F[1]=1;
if (cin >> n) {
if (n==0)
cout << 0 << endl;
else
cout << f(n-1, 0) << endl;
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgbG9uZyBsb25nIGxvbmcKY29uc3QgbG9uZyBNID0gMTAwMDAwMDAwNzsgLy8gbW9kdWxvCgptYXA8bG9uZywgbG9uZz4gRjsKdmVjdG9yPGxvbmc+IFRbMTIzNF07Cgpsb25nIGYobG9uZyBuLCBpbnQgRGVwdGgpIHsKCVRbRGVwdGhdLnB1c2hfYmFjayhuKTsKCWlmIChGLmNvdW50KG4pKSByZXR1cm4gRltuXTsKCWxvbmcgaz1uLzI7CglpZiAobiUyPT0wKSB7IC8vIG49MiprCgkJcmV0dXJuIEZbbl0gPSAoZihrLCBEZXB0aCsxKSpmKGssIERlcHRoKzEpICsgZihrLTEsIERlcHRoKzEpKmYoay0xLCBEZXB0aCsxKSkgJSBNOwoJfSBlbHNlIHsgLy8gbj0yKmsrMQoJCXJldHVybiBGW25dID0gKGYoaywgRGVwdGgrMSkqZihrKzEsIERlcHRoKzEpICsgZihrLTEsIERlcHRoKzEpKmYoaywgRGVwdGgrMSkpICUgTTsKCX0KfQoKbWFpbigpewoJbG9uZyBuOwoJRlswXT1GWzFdPTE7CglpZiAoY2luID4+IG4pIHsKCQlpZiAobj09MCkgCgkJCWNvdXQgPDwgMCA8PCBlbmRsOwoJCWVsc2UgCgkJCWNvdXQgPDwgZihuLTEsIDApIDw8IGVuZGw7Cgl9Cgp9