> import java.io.*;
> import java.util.*;
> 
> public class Main {
> 	public static void main(String[] args) throws Exception{
> 		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
> 		String line=null;
> 			line=br.readLine();
> 			final int MAX = 1000000000;
> 			int n=Integer.parseInt(line),M[]=new int[n+1];
> 			M[1]=1;
> 			M[2]=2;
> 			for(int i=3;i<=n;i++){
> 				M[i]=i%2==0?M[i-2]+M[i>>1]:M[i-1];
> 				M[i]=M[i]>MAX?M[i]%MAX:M[i];
> 			}
> 			System.out.println(M[n]);
> 	}
> }
> 
>