#include<stdio.h>
memoization
int memo[100000] = {0};
int rec(int n){
if(n<=3) return memo[n] = n;
if(memo[n]!=0) return memo[n];
return memo[n] = (rec(n-1)%100000007 + rec(n-2)%100000007)%100000007;
}
int main()
{
int n;
int i,j;
scanf("%d", &n);
printf("%d", rec(n%100000007));
}
#include<stdio.h>
int memo[100000]={0};
int rec(int n)
{
if(n==3) return memo[n] = 2;
if(n%3!=0) return memo[n] = 0;
if (memo[n]!=0) return memo[n];
return memo[n] = (rec(n-3)*2)%100000007; // 왜 안될까
}
int main()
{
int n;
scanf("%d", &n);
memo[3] = 2;
memo[6] = 4;
memo[9] = 8;
memo[12] = 16;
printf("%d", rec(n)%100000007);
}
#include<stdio.h>
int memo[100000]={0};
int rec(int n)
{
if(n==1) return memo[n] = 1;
if(n==2) return memo[n] = 3;
if(n==3) return memo[n] = 5;
if(memo[n]!=0) return memo[n];
return memo[n] = rec(n-2)%100007+rec(n-2)%100007+rec(n-1)%100007;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n)%100007);
}
#include<stdio.h>
int memo[100000] = {0};
int cnt=0;
int rec(int n)
{
if(memo[n]!=0)
if(n==1) return 1;
if(n%2==0) return rec(n/2);
if(n%2==1) return rec((3*n)+1);
cnt = cnt + 1;
}
int main()
{
int a,b,n,i;
int m=-1;
scanf("%d %d", &a, &b);
for(i=a;i<=b;i++)
{
i = n;
rec(n);
if(rec(n)>m)
{
m = rec(n);
}
}
printf("%d %d", m, cnt);
}