1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}());
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a,int b) { return b?gcd(b,a%b):a;}
// head

const int N=1100000;

#define INF 0x3f3f3f3f

template<class T> inline void read(T &x) {
    x=0; int c=getchar(),f=1;
    for (;!isdigit(c);c=getchar()) if (c==45) f=-1;
    for (;isdigit(c);c=getchar()) (x*=10)+=f*(c-'0');
}

VI LCMs={1,2,3,6,4,12,5,10,15,30,20,60,7,14,21,42,28,84,35,70,105,210,140,420,8,24,40,120,56,168,280,840,9,18,36,45,90,180,63,126,252,315,630,1260,72,360,504,2520};

int pot10[20],LCMsPos[3000];
ll dp[20][2][50][2520],partialAns[18]={0,9,23,79,339,1645,9039,52990,326499,2087730,13723041,92274986,631897069,4394553406,30974247501,220912332916,1592387930894,11589229677560},
ans[2];

char NUM[2][20];

bool check() {
	int len=strlen(NUM[0]+1);
	ll sum=0;
	rep(i,1,len+1) sum*=10,sum+=NUM[0][i]-'0';
	rep(i,1,len+1) if (sum%(NUM[0][i]-'0')!=0) return false;
	return true;
}

int main() {
	rep(i,0,SZ(LCMs)) LCMsPos[LCMs[i]]=i;
	scanf("%s%s",NUM[0]+1,NUM[1]+1);
	pot10[0]=1;
	rep(i,1,20) pot10[i]=pot10[i-1]*10%2520;
	rep(nr,0,2) {
		memset(dp,0,sizeof(dp));
		int len=strlen(NUM[nr]+1);
		dp[len+1][0][0][0]=1;
		per(i,1,len+1) rep(j,0,2) rep(k,0,47) rep(l,0,2520) {
			int c=NUM[nr][len-i+1]-'0';
			if (j==0&&c!=0&&LCMs[k]%c==0) {
				int target=(l-pot10[i-1]*c%2520+2520)%2520;
				dp[i][j][k][l]+=dp[i+1][0][k][target];
				if (c==2) {if ((LCMs[k]/2)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target];}
				else if (c==3) {if ((LCMs[k]/3)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/3]][target];}
				else if (c==4) {if ((LCMs[k]/4)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target]+dp[i+1][0][LCMsPos[LCMs[k]/4]][target];}
				else if (c==5) {if ((LCMs[k]/5)%5!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/5]][target];}
				else if (c==6) {
					if ((LCMs[k]/6)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target];
					if ((LCMs[k]/6)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/3]][target];
					if ((LCMs[k]/6)%2!=0&&(LCMs[k]/6)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/6]][target];
				}
				else if (c==7) {if ((LCMs[k]/7)%7!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/7]][target];}
				else if (c==8) {if ((LCMs[k]/8)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target]+dp[i+1][0][LCMsPos[LCMs[k]/4]][target]+dp[i+1][0][LCMsPos[LCMs[k]/8]][target];}
				else if (c==9) {if ((LCMs[k]/9)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/3]][target]+dp[i+1][0][LCMsPos[LCMs[k]/9]][target];}
			}
			else if (j==1) {
				int target=(l-pot10[i-1]%2520+2520)%2520;
				dp[i][j][k][l]+=dp[i+1][1][k][target];
				if (1<c) dp[i][j][k][l]+=dp[i+1][0][k][target];
				if (LCMs[k]%2==0) {
					target=(l-pot10[i-1]*2%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/2)%2!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/2]][target];
					if (2<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/2)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target];
					}
				}
				if (LCMs[k]%3==0) {
					target=(l-pot10[i-1]*3%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/3)%3!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/3]][target];
					if (3<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/3)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/3]][target];
					}
				}
				if (LCMs[k]%4==0) {
					target=(l-pot10[i-1]*4%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/4)%2!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/2]][target]+dp[i+1][1][LCMsPos[LCMs[k]/4]][target];
					if (4<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/4)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target]+dp[i+1][0][LCMsPos[LCMs[k]/4]][target];
					}
				}
				if (LCMs[k]%5==0) {
					target=(l-pot10[i-1]*5%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/5)%5!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/5]][target];
					if (5<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/5)%5!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/5]][target];
					}
				}
				if (LCMs[k]%6==0) {
					target=(l-pot10[i-1]*6%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/6)%2!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/2]][target];
					if ((LCMs[k]/6)%3!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/3]][target];
					if ((LCMs[k]/6)%2!=0&&(LCMs[k]/6)%3!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/6]][target];
					if (6<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/6)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target];
						if ((LCMs[k]/6)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/3]][target];
						if ((LCMs[k]/6)%2!=0&&(LCMs[k]/6)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/6]][target];
					}
				}
				if (LCMs[k]%7==0) {
					target=(l-pot10[i-1]*7%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/7)%7!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/7]][target];
					if (7<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/7)%7!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/7]][target];
					}
				}
				if (LCMs[k]%8==0) {
					target=(l-pot10[i-1]*8%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/8)%2!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/2]][target]+dp[i+1][1][LCMsPos[LCMs[k]/4]][target]+dp[i+1][1][LCMsPos[LCMs[k]/8]][target];
					if (8<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/8)%2!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/2]][target]+dp[i+1][0][LCMsPos[LCMs[k]/4]][target]+dp[i+1][0][LCMsPos[LCMs[k]/8]][target];
					}
				}
				if (LCMs[k]%9==0) {
					target=(l-pot10[i-1]*9%2520+2520)%2520;
					dp[i][j][k][l]+=dp[i+1][1][k][target];
					if ((LCMs[k]/9)%3!=0) dp[i][j][k][l]+=dp[i+1][1][LCMsPos[LCMs[k]/3]][target]+dp[i+1][1][LCMsPos[LCMs[k]/9]][target];
					if (9<c) {
						dp[i][j][k][l]+=dp[i+1][0][k][target];
						if ((LCMs[k]/9)%3!=0) dp[i][j][k][l]+=dp[i+1][0][LCMsPos[LCMs[k]/3]][target]+dp[i+1][0][LCMsPos[LCMs[k]/9]][target];
					}
				}
			}
		}
		rep(i,0,SZ(LCMs)-1) rep(j,0,2520) if (j%LCMs[i]==0) ans[nr]+=dp[1][1][i][j]+dp[1][0][i][j];
		ans[nr]+=partialAns[len-1];
	}
	printf("%lld\n",ans[1]-ans[0]+check());
}