#include<bits/stdc++.h> #define ll long long using namespace std; const ll mod=20090219; const int N=1e7+7; int Fac[N],iFac[N]; 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; iFac[0]=iFac[1]=1; for(int i=2;i<N;i++)iFac[i]=1ll*iFac[mod%i]*(mod-mod/i)%mod; for(int i=2;i<N;i++)iFac[i]=1ll*iFac[i-1]*iFac[i]%mod; } inline ll C(int n,int m){ return n<m||m<0?0:1ll*Fac[n]*1ll*iFac[m]%mod*1ll*iFac[n-m]%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); } inline ll slv3(string S){//2,3,6 if(S=="")return 1; int L=S.length(); SP="";ll ret=1; for(int i=0;i<L;i++){ if(S[i]=='6')(ret*=slv4(SP))%=mod,SP=""; else SP+=S[i]; }(ret*=slv4(SP))%=mod; SP.clear();SP.shrink_to_fit(); 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*slv3(SP)%mod; SP.clear();SP.shrink_to_fit(); return P; } inline ll slv1(string S){//0,2,3,5,6,7 if(S=="")return 1; int L=S.length(); SP="";ll ret=1; for(int i=0;i<L;i++){ if(S[i]=='0')(ret*=slv2(SP))%=mod,SP=""; else SP+=S[i]; }(ret*=slv2(SP))%=mod; SP.clear();SP.shrink_to_fit(); 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)*slv1(SP)%mod; SP.clear();SP.shrink_to_fit(); return P; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("chchch.in","r",stdin); freopen("chchch.out","w",stdout); #endif 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; }