최, 재롱 자신감

시간 제한 1000ms
메모리 제한 65536KB

제목 설명

최개그는 선량한 선배로 후배를 위해 출제하는 것을 가장 좋아한다.그는 모두에게 정수 n을 하나 주어 0<=x<=n의 범위 내에서 몇 개의 수가 (x)^(2x)^(3x)===0(^는 이상 또는 기호)을 만족시킬 수 있는지 구했다.너는 그에게 1000000009에 대한 나머지 답안만 알려주면 된다.

입력 형식

여러 그룹의 데이터를 입력하고 수량은 100 이내이며 줄마다 정수 n(0<=n<=10^18)을 입력합니다.

출력 형식

각 그룹의 데이터가 한 줄의 답안을 출력합니다.

샘플 가져오기

1
2

출력 예제

2
3

  ：(i^(2*i)^(3*i))==0 --- i^(2*i)==3*i==i+2*i--- 2*i    i  1 ，        1 ，       。

     ，   n           f(n),  f(n)=f(n-1)+f(n-2)

      n  ，  ，    0，sum+=f(len-1)

		    1，     ，      1，sum+=f(len-2)

					    0，        1，    。

  ：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#define MOD 1000000009
using namespace std;
long long f[100];
long long sum;
int num[100];
void get(int len)
{
    if(len==1&&num[0]==1)
        sum+=2;
    else
    {
        sum=(sum+f[len-1])%MOD;
        if(len>=2)
        {
            if(num[len-2]==1)
                sum=(sum+f[len-2])%MOD;
            else
            {
                int j=len-2;
                while(j>=0&&num[j]==0)
                    j--;
                if(j<0)
                {
                    sum=(sum+1)%MOD;
                }
                else
                   get(j+1);
            }
        }
    }

}
int main()
{
    long long n,i;
    int len;
    f[0]=1;f[1]=2;f[2]=3;
    for(i=3;i<100;i++)
    {
        f[i]=(f[i-1]+f[i-2])%MOD;
    }
    while(scanf("%lld",&n)!=EOF)
    {
        sum=0;
        if(n==0)
            printf("1
");
        else
        {
            len=0;
            while(n)
            {
                num[len]=n%2;
                n>>=1;
                len++;
            }
            get(len);
            printf("%lld
",sum);
        }
    }
    return 0;
}