1 #include <cstdio>

  2 #include <cstdlib>

  3 #include <cstring>

  4 #include <cmath>

  5 #include <iostream>

  6 #include <algorithm>

  7 #include <map>

  8 #include <queue>

  9 #include <vector>

 10 #include<set>

 11 using namespace std;

 12 typedef long long LL;

 13 bool flag[6000000];

 14 int ans[20];

 15 set<int>que;

 16 set<int>::iterator it;

 17 typedef struct pp

 18 {

 19         int mod;

 20         int id;

 21         int pre;

 22         int digit;

 23         pp()

 24         {

 25             pre=-1;

 26         }

 27 } ss;

 28 ss bns[1000000];

 29 int ask[1000000];

 30 int cp[2000000];

 31 int  bfs(int n,int m);

 32 int main(void)

 33 {

 34         int i,j,k;

 35         while(scanf("%d",&k)!=EOF)

 36         {

 37                 int n;

 38                 int m;

 39                 que.clear();

 40                 cp[0] = 0;cp [1] = 1;

 41                 n = 2;

 42                  ans[0]=cp[0];

 43                 int uu=cp[0];

 44                 int t=1;

 45                  for(i=1;i<n;i++)

 46                  {

 47                      if(cp[i]!=uu)

 48                      {

 49                          ans[t++]=cp[i];

 50                          uu=cp[i];

 51                      }

 52                  }

 53

 54                 if(k==0)printf("0\n");

 55                 else

 56                 {

 57                         int sum=0;

 58                         int id=bfs(t,k);

 59                         if(id==-1)

 60                         {

 61                                 printf("0\n");

 62                         }

 63                         else

 64                         {

 65                                 while(id!=-1)

 66                                 {

 67                                         ask[sum++]=bns[id].digit;

 68                                         id=bns[id].pre;

 69                                 }

 70                                 for(i=sum-1; i>=0; i--)

 71                                 {

 72                                         printf("%d",ask[i]);

 73                                 }

 74                                 printf("\n");

 75                         }

 76                 }

 77         }

 78         return 0;

 79 }

 80 int  bfs(int n,int m)

 81 {

 82         int i,j,k;

 83         int kk=0;

 84         memset(flag,0,sizeof(flag));

 85         queue<ss>stc;

 86         for(i=0; i<n; i++)

 87         {

 88                 int mod=ans[i]%m;

 89                 if(!flag[mod]&&ans[i]!=0)

 90                 {

 91                         flag[mod]=true;

 92                         bns[kk].id=kk;

 93                         bns[kk].mod=mod;

 94                         bns[kk].pre=-1;

 95                         bns[kk].digit=ans[i];

 96                         stc.push(bns[kk]);

 97                         kk++;

 98                 }

 99         }

100         while(!stc.empty())

101         {

102                 ss tt=stc.front();

103                 stc.pop();

104                 for(i=0; i<n; i++)

105                 {

106                         int mod=(tt.mod*10+ans[i])%m;

107                         if(!flag[mod])

108                         {

109                                 bns[kk].id=kk;

110                                 bns[kk].pre=tt.id;

111                                 bns[kk].mod=mod;

112                                 bns[kk].digit=ans[i];

113                                 if(mod==0)

114                                 {

115                                         return kk;

116                                 }

117                                 stc.push(bns[kk]);

118                                 kk++;

119                                 flag[mod]=true;

120                         }

121                 }

122         }

123         return -1;

124 }