#include<bits/stdc++.h> using namespace std; #define ll long long int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=10000010,Mod=20090219; ll Pow(ll x,int y){ll rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod;y>>=1;}return rt;} void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;if(x<0)x+=Mod;} int n,m,cnt,jc[MAXN],ny[MAXN]; ll ans; char s[MAXN]; ll C(int x,int y){return (ll)jc[x]*ny[y]%Mod*ny[x-y]%Mod;} ll sol(int l,int r){if(l>r)return 1; ll res=1; int k=0,cnt5=0,cnt7=0; for(int i=l;i<=r;i++){ if(s[i]=='5')cnt5++; else if(s[i]=='7')cnt7++; else s[++k]=s[i]; } int lst=0; for(int i=1;i<=k+1;i++){ if(i==k+1||s[i]=='6'){ int cnt2=0,cnt3=0; for(int j=lst+1;j<i;j++)if(s[j]=='3'||s[j]=='9')cnt3++;else cnt2++; res=res*C(cnt2+cnt3,cnt2)%Mod; lst=i; } } return res*C(k+cnt5,cnt5)%Mod*C(k+cnt5+cnt7,cnt7)%Mod; } void slv(){ scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++)if(s[i]!='1')s[++m]=s[i];else cnt++; n=m; int lst=0; ans=1; for(int i=1;i<=m+1;i++) if(i==m+1||s[i]=='0')ans=ans*sol(lst+1,i-1)%Mod,lst=i; printf("%lld",ans*C(n+cnt,cnt)%Mod); } signed main(){ // freopen("chchch.in","r",stdin);freopen("chchch.out","w",stdout); jc[0]=ny[0]=1; for(int i=1;i<=MAXN-5;i++)jc[i]=(ll)jc[i-1]*i%Mod; ny[MAXN-5]=Pow(jc[MAXN-5],Mod-2); for(int i=MAXN-6;i>=1;i--)ny[i]=(ll)ny[i+1]*(i+1)%Mod; // int _=read();while(_--) slv(); // system("grep VmPeak /proc/$PPID/status"); return 0; }