#include<bits/stdc++.h> #define ll long long using namespace std; template<typename T> void read(T &x){x=0;bool neg=0;char c=getchar();while(!isdigit(c)){if(c=='-')neg=1;c=getchar();}while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();if(neg)x=-x;} #define read2(a,b) read(a),read(b) #define read3(a,b,c) read2(a,b),read(c) #define read4(a,b,c,d) read3(a,b,c),read(d) #define read5(a,b,c,d,e) read4(a,b,c,d),read(e) #define read6(a,b,c,d,e,f) read5(a,b,c,d,e),read(f) const int mod=20090219; string s,t; int n,cnt1; ll ans=1; int fact[10000005],inv[10000005]; int qp(ll x,int y){ ll res=1; while(y){ if(y&1)res*=x,res%=mod; x*=x,x%=mod; y>>=1; } return res; } int C(int x,int y){ return 1ll*fact[x]*inv[y]%mod*inv[x-y]%mod; } int calc(int l,int r){ t.clear(); t.push_back(' '); for(int i=l;i<=r;i++)if(s[i]!='1')t.push_back(s[i]); int m=t.size()-1; int cnt2=0,cnt3=0; ll res=1; for(int i=1;i<=m;i++){ if((t[i]-'0')%2==0)cnt2++; if((t[i]-'0')%3==0)cnt3++; if(t[i]=='6')res*=C(cnt2+cnt3-2,cnt3-1),res%=mod,cnt2=cnt3=0; // cout<<cnt2<<" "<<cnt3<<" "<<res<<endl; } res*=C(cnt2+cnt3,cnt3),res%=mod,cnt2=cnt3=0; // cout<<cnt2<<" "<<cnt3<<" "<<res<<endl; int cnt5=0,cnt7=0; for(int i=1;i<=m;i++){ if(t[i]=='5')cnt5++; if(t[i]=='7')cnt7++; } res*=C(m,cnt5); res%=mod; res*=C(m-cnt5,cnt7); res%=mod; return res; } void slv(){ cin>>s; n=s.size(); s=' '+s; for(int i=1;i<=n;i++)if(s[i]=='1')cnt1++; for(int i=1,lst=0;i<=n;i++){ if(s[i]=='0'){ if(i-1>=lst+1)ans*=calc(lst+1,i-1),ans%=mod; lst=i; } else if(i==n&&lst<n)ans*=calc(lst+1,n),ans%=mod; } ans*=C(n,cnt1); ans%=mod; cout<<ans<<endl; } signed main(){ fact[0]=1; for(int i=1;i<=10000000;i++)fact[i]=1ll*fact[i-1]*i%mod; inv[10000000]=qp(fact[10000000],mod-2); for(int i=9999999;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod; // int T;read(T);while(T--) slv(); return 0; }