#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 20090219; string a; signed n; signed b[10000007],c[10000007]; int cnt[10]; inline int pw (int x,int y) { int r = 1; while (y) { if (y & 1) { r = r * x % mod; } x = x * x % mod; y >>= 1; } return r; } inline int C (int n,int m) { return 1ll * b[n] * c[n - m] % mod * c[m] % mod; } signed main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> a; n = a.size(); a = ' ' + a; for (int i = 1;i <= n;i++) { a[i] -= '0'; if (a[i] == 4 || a[i] == 8) { a[i] = 2; } if (a[i] == 9) { a[i] = 3; } } b[0] = 1; for (int i = 1;i <= n;i++) { b[i] = 1ll * b[i - 1] * i % mod; } c[n] = pw(b[n],mod - 2); for (int i = n - 1;i >= 1;i--) { c[i] = 1ll * c[i + 1] * i % mod; } int ans = 1; int sp = 0; for (int i = 1;i <= n + 1;i++) { cnt[a[i]]++; if (a[i] == 6 || a[i] == 0) { ans *= C(cnt[2] + cnt[3],cnt[2]); ans %= mod; cnt[2] = 0; cnt[3] = 0; } if (a[i] == 0) { ans *= C(sp,cnt[5] + cnt[7]); ans %= mod; ans *= C(cnt[5] + cnt[7],cnt[7]); ans %= mod; sp = 0; cnt[5] = 0; cnt[7] = 0; } if (a[i] > 1) { sp++; } } ans *= C(n,cnt[1]); ans %= mod; cout << ans << endl; return 0; }