/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=1e9+9;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int f[2][1<<10][2],g[2][1<<10][2];
int to[1<<10][10];
int n;
void add(int &x,int y)
{
	x+=y;
	if(x>=mod) x-=mod;
}
int calc(string lim)
{
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(int i=0;i+'0'<=lim[0];i++)
	{
		int tp=(i+'0'<lim[0]?1:0);
		g[0][(i==0?0:(1<<i))][tp]++,f[0][(i==0?0:(1<<i))][tp]+=(10-i)%10;
	}
	int nw=0;
	for(int i=1;i<n;i++)
	{
		nw^=1;
		memset(f[nw],0,sizeof(f[nw])),memset(g[nw],0,sizeof(g[nw]));
		for(int mask=0;mask<(1<<10);mask++) for(int tp=0;tp<2;tp++) if(f[nw^1][mask][tp]||g[nw^1][mask][tp])
		{
			for(int d=0;d<10;d++)
			{
				if(tp==0&&d+'0'>lim[i]) continue;
				int tp2=tp;
				if(d+'0'<lim[i]) tp2=1;
				if(to[mask][d]!=-1) add(f[nw][to[mask][d]][tp2],f[nw^1][mask][tp]),add(g[nw][to[mask][d]][tp2],g[nw^1][mask][tp]);
				else
				{
					add(f[nw][mask^(1<<d)][tp2],(f[nw^1][mask][tp]+10LL*g[nw^1][mask][tp])%mod),add(g[nw][mask^(1<<d)][tp2],g[nw^1][mask][tp]);
				}
			}
		}
	}
	int ans=0;
	for(int mask=0;mask<(1<<10);mask++) for(int tp=0;tp<2;tp++) add(ans,f[nw][mask][tp]);
	return ans;
}
string L,R;
void solve()
{
	cin>>n;
	cin>>L>>R;
	L[L.size()-1]--;
	for(int i=L.size()-1;i>=0;i--)
	{
		if(L[i]<'0') L[i]+=10,L[i-1]--;
		else break;
	}
	memset(to,-1,sizeof(to));
	for(int mask=0;mask<(1<<10);mask++) for(int i=0;i<10;i++) 
	{
		if(!i)
		{
			to[mask][i]=mask;
			continue;
		}
		for(int j=i;j>=0;j--) if(mask&(1<<j))
	{
		to[mask][i]=(mask^(1<<j)^(1<<i));
		break;
	}
	}
//	cout<<L<<" "<<R<<" "<<calc(L)<<" "<<calc(R)<<"\n";
	cout<<(calc(R)-calc(L)+mod)%mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}