#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]*iFac[m]%mod*iFac[n-m]%mod; } string S; inline ll slv2(int l,int r){ int C3=0,C2=0; for(int i=l;i<=r;i++){ if(S[i]=='3')C3++; if(S[i]=='2')C2++; }return C(C3+C2,C2); } inline ll slv1(int l,int r){//2,3,5,6,7 int C5=0,C7=0,lst=l-1,L=0; ll ret=1; for(int i=l;i<=r;i++){ if(S[i]=='1')continue; L++; C5+=(S[i]=='5');C7+=(S[i]=='7'); if(S[i]=='6')(ret*=slv2(lst+1,i-1))%=mod,lst=i; }(ret*=slv2(lst+1,r))%=mod; (ret*=C(C5+C7,C5)*C(L,C5+C7)%mod)%=mod; return ret; } 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'; } int C1=0,lst=-1; ll ret=1; for(int i=0;i<L;i++){ C1+=(S[i]=='1'); if(S[i]=='0'){ (ret*=slv1(lst+1,i-1))%=mod; lst=i; } }(ret*=slv1(lst+1,L-1))%=mod; (ret*=C(L,C1))%=mod; cout<<ret<<endl; return 0; }