#include<bits/stdc++.h> using namespace std; const int md = 20090219,N = 1e7+10; int pre[N],inv[N],ans; int n,a[N]; int quickpow(int x,int y){ int tmp=1; while(y){ if(y&1) tmp=tmp%md*x%md; y=y>>1; x=x%md*x%md; } return tmp; } int C(int x,int y){ if(x<y) return 0; else if(y==0) return 1; else return pre[x]%md*inv[y]%md*inv[x-y]%md; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); char x; while(cin>>x){ a[++n]=x-'0'; } pre[0]=1; for(int i=1;i<=n;i++){ pre[i]=pre[i-1]%md*i%md; } inv[n]=quickpow(pre[n],md-2)%md; for(int i=n-1;i>=0;i--){ inv[i]=inv[i+1]%md*(i+1)%md; } int num_1=0; for(int i=1;i<=n;i++){ if(a[i]==1) num_1++; } ans=C(n,num_1); int num=0,num_5=0,num_7=0; for(int i=1;i<=n;i++){ if(a[i]==0){ ans=ans%md*C(num,num_5+num_7)%md*C(num_5+num_7,num_5)%md; num_5=0; num_7=0; num=0; } else if(a[i]==5){ num_5++; num++; } else if(a[i]==7){ num_7++; num++; } else if(a[i]!=1){ num++; } } ans=ans%md*C(num,num_5+num_7)%md*C(num_5+num_7,num_5)%md; int num_e=0,num_o=0; for(int i=1;i<=n;i++){ if(a[i]==0||a[i]==6){ ans=ans%md*C(num_e+num_o,num_e)%md; num_e=0; num_o=0; } else if(a[i]==2||a[i]==4||a[i]==8){ num_e++; } else if(a[i]==3||a[i]==9){ num_o++; } } ans=ans%md*C(num_e+num_o,num_e)%md; ans=(ans+md)%md; printf("%d\n",ans); return 0; }