#include<bits/stdc++.h> #define ll long long using namespace std; const ll mod=20090219; const int N=1e7+7; bool ST; int Fac[N]; bool ED; inline ll qpow(ll a,int b){ ll Ans=1; while(b){ if(b&1)Ans=Ans*a%mod; a=a*a%mod; b>>=1; }return Ans; } inline void Init(){ Fac[0]=1; for(int i=1;i<N;i++)Fac[i]=1ll*Fac[i-1]*i%mod; } inline ll C(int n,int m){ return n<m||m<0?0:1ll*Fac[n]*1ll*qpow(Fac[m],mod-2)%mod*1ll*qpow(Fac[n-m],mod-2)%mod; } string SP=""; string S=""; inline ll slv4(string S){//2,3 if(S=="")return 1; int L=S.length(); int C2=0; for(int i=0;i<L;i++)if(S[i]=='2')C2++; return C(L,C2); } int OCC1[N],OCC2[N],tp1,tp2; inline ll slv3(string S){//2,3,6 if(S=="")return 1; tp2=0; OCC2[tp2++]=-1; int L=S.length(); for(int i=0;i<L;i++)if(S[i]=='6')OCC2[tp2++]=i; OCC2[tp2++]=L; ll ret=1; for(int i=0;i<tp2-1;i++){ SP=""; for(int j=OCC2[i]+1;j<OCC2[i+1];j++)SP+=S[j]; ret=1ll*ret*slv4(SP)%mod; }return ret; } inline ll slv2(string S){//2,3,5,6,7 if(S=="")return 1; int L=S.length(); int C5=0,C7=0; SP=""; for(auto ch:S){ if(ch=='5')C5++; else if(ch=='7')C7++; else SP+=ch; } ll P=1ll*C(L,C5)*C(L-C5,C7)%mod; return 1ll*P*slv3(SP)%mod; } inline ll slv1(string S){//0,2,3,5,6,7 if(S=="")return 1; for(int i=0;i<tp1;i++)OCC1[i]=0; tp1=0; OCC1[tp1++]=-1; int L=S.length(); for(int i=0;i<L;i++)if(S[i]=='0')OCC1[tp1++]=i; OCC1[tp1++]=L; ll ret=1; for(int i=0;i<tp1-1;i++){ SP=""; for(int j=OCC1[i]+1;j<OCC1[i+1];j++)SP+=S[j]; ret=1ll*ret*slv2(SP)%mod; }return ret; } inline ll slv0(string S){//0,1,2,3,5,6,7 int L=S.length(); int C1=0; SP=""; for(int i=0;i<L;i++){ if(S[i]!='1')SP+=S[i]; else C1++; } ll P=C(L,C1); return 1ll*P*slv1(SP)%mod; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); Init(); char t=getchar(); while('0'<=t&&t<='9'){ S+=t; t=getchar(); } int L=S.length(); for(int i=0;i<L;i++){ if(S[i]=='4'||S[i]=='8')S[i]='2'; if(S[i]=='9')S[i]='3'; } cout<<slv0(S)<<endl; return 0; }