#include<bits/stdc++.h> #define ll long long using namespace std; const int mod=20090219; void testread(){freopen("chchch/chchch6.in","r",stdin);freopen("test.out","w",stdout);} void fastios(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);} void realread(){freopen("chchch.in","r",stdin);freopen("chchch.out","w",stdout);} ll fpow(ll n,ll x){ ll s=1; while(x){ if(x&1) s=s*n%mod; x>>=1,n=n*n%mod; } return s; } char s[10000010]; int N,fac[10000010],inv[10000010]; inline ll C(int n,int m){ if(n==m) return 1; if(n<m||m<0) return 0; return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod; } ll solve2(int l,int r){ int cnt1=0,cnt2=0; for(int i=l;i<=r;i++) cnt1+=(s[i]-48)%2==0,cnt2+=(s[i]-48)%3==0; return C(cnt1+cnt2,cnt1); } ll solve1(int l,int r){ int cnt5=0,cnt7=0,cnt=0,lst=l-1; ll ans=1; for(int i=l;i<=r;i++){ cnt5+=s[i]=='5',cnt7+=s[i]=='7',cnt+=s[i]!='1'; if(s[i]=='6') (ans*=solve2(lst+1,i-1))%=mod,lst=i; } (ans*=solve2(lst+1,r))%=mod; ans=ans*C(cnt5+cnt7,cnt5)%mod*C(cnt,cnt5+cnt7)%mod; return ans; } signed main(){ fastios(); //testread(); //realread(); cin>>s; N=int(strlen(s)); fac[0]=1; for(int i=1;i<=N;i++) fac[i]=int(1LL*fac[i-1]*i%mod); inv[N]=int(fpow(fac[N],mod-2)); for(int i=N-1;~i;i--) inv[i]=int(1LL*inv[i+1]*(i+1)%mod); int cnt1=0,lst=-1; ll ans=1; for(int i=0;i<N;i++){ cnt1+=s[i]=='1'; if(s[i]=='0') (ans*=solve1(lst+1,i-1))%=mod,lst=i; } (ans*=solve1(lst+1,N-1))%=mod; ans=ans*C(N,cnt1)%mod; cout<<ans; return 0; }