Fox Ciel studies number theory.

She thinks a non-empty set *S* contains non-negative integers is perfect if and only if for any <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/9ef9929d40fa162bdd76a55da469dde6fc13a5f5.png" style="max-width: 100.0%;max-height: 100.0%;"/> (*a* can be equal to *b*), <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/bba2b10c821617f53f33d4f198ad3dfee0eb6ecd.png" style="max-width: 100.0%;max-height: 100.0%;"/>. Where operation *xor* means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than *k*. The answer can be very large, so print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains an integer *k* (0 ≤ *k* ≤ 10<sup class="upper-index">9</sup>).
k=int(input())
mod=10**9+7
ans=1
for i in range(k):
    ans+=(ans^i)
print(ans%mod)