/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.HashMap;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{	 static long M=1000000007;
	 static HashMap<Long,Long> hm=new HashMap<Long,Long>();
	public static void main (String[] args) throws java.lang.Exception
	{
		hm.put(1L,1L);
       hm.put(0L,1L);
       long b=f(3L);
		// your code goes here
	}
	
	static long  f(long n) {
	if (hm.containsKey(n)) return hm.get(n);
	System.out.println("n="+n);
	long k=n/2;
	if (n%2==0) {
		return hm.put(n,f(k)*(f(k+1)+f(k-1)) % M);
                
	} else { 
		return hm.put(n, (f(k+1)*f(k+1) + f(k)*f(k)) % M);
       }
}
}