[AC 자동기] ZOJ 3494 BCD 코드.

#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <time.h>
#define maxn 2005
#define maxm 60005
#define eps 1e-7
#define mod 1000000009
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#define lowbit(x) (x&(-x))
#define mp make_pair
#define ls o<<1
#define rs o<<1 | 1
#define lson o<<1, L, mid 
#define rson o<<1 | 1, mid+1, R
#define pii pair<int, int>
#pragma comment(linker, "/STACK:16777216")
typedef long long LL;
typedef unsigned long long ULL;
//typedef int LL;
using namespace std;
LL qpow(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base;base=base*base;b/=2;}return res;}
LL powmod(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base%mod;base=base*base%mod;b/=2;}return res;}
//head

const int o = 2;

struct AC
{
	int next[maxn][o];
	int fail[maxn];
	int end[maxn];
	char s[maxn];
	queue<int> q;
	int root, now, tail;

	int newnode()
	{
		end[tail] = 0;
		fail[tail] = -1;
		memset(next[tail], -1, sizeof next[tail]);
		return tail++;
	}

	void init()
	{
		tail = 0;
		root = newnode();
	}

	void insert()
	{
		scanf("%s", s);
		now = root;
		for(int i = 0; s[i]; i++) {
			int t = s[i] - '0';
			if(next[now][t] == -1) next[now][t] = newnode();
			now = next[now][t];
		}
		end[now] = true;
	}

	void bfs()
	{
		now = root;
		for(int i = 0; i < o; i++)
			if(next[now][i] == -1) next[now][i] = root;
			else {
				q.push(next[now][i]);
				fail[next[now][i]] = root;
			}
		while(!q.empty()) {
			now = q.front();
			q.pop();
			end[now] |= end[fail[now]];
			for(int i = 0; i < o; i++)
				if(next[now][i] == -1) next[now][i] = next[fail[now]][i];
				else {
					q.push(next[now][i]);
					fail[next[now][i]] = next[fail[now]][i];
				}
		}
	}
};

AC ac;
LL dp[2005][205];
char digit[maxn];
int n, mx;

int check(int u, int t)
{
	int ok = 0;
	if(t <= 7) u = ac.next[u][0];
	else u = ac.next[u][1];
	ok |= ac.end[u];

	if(t >= 4 && t <= 7) u = ac.next[u][1];
	else u = ac.next[u][0];
	ok |= ac.end[u];

	if(t == 2 || t == 3 || t == 6 || t == 7) u = ac.next[u][1];
	else u = ac.next[u][0];
	ok |= ac.end[u];

	if(t % 2) u = ac.next[u][1];
	else u = ac.next[u][0];
	ok |= ac.end[u];
	
	if(ok) return -1;
	else return u;
}

LL dfs(int u, int pos, int limit, int oo)
{
	if(dp[u][pos] != -1 && !limit && !oo) return dp[u][pos];
	if(pos == 0) return true;
	LL ans = 0;
	int a = (oo && pos != 1) ? 1 : 0;
	int b = limit ? digit[pos] - '0' : 9;
	for(int i = a; i <= b; i++) {
		int t = check(u, i);
		if(t == -1) continue;
		ans = (ans + dfs(t, pos-1, limit & (i == b), 0)) % mod;
	}
	if(oo && pos != 1) ans = (ans + dfs(u, pos-1, limit & (b == 0), oo)) % mod;
	if(!limit) dp[u][pos] = ans;
	return ans;
}

bool judge(int pos)
{
	int u = 0, ok = 0;
	for(int i = pos; i > 0; i--) {
		int t = check(u, digit[i] - '0');
		if(t == -1) return 0;
		u = t;
	}
	return 1;
}

void work()
{
	ac.init();
	scanf("%d", &n);
	for(int i = 0; i < n; i++) ac.insert();
	ac.bfs();
	
	LL ans = 0;
	memset(dp, -1, sizeof dp);
	scanf("%s", digit+1);
	int len = strlen(digit+1);
	mx = len;
	reverse(digit+1, digit+len+1);
	ans = (ans - dfs(0, len, 1, 1)) % mod;
	ans = (ans + judge(len)) % mod;
	
	scanf("%s", digit+1);
	mx = len = strlen(digit+1);
	reverse(digit+1, digit+len+1);
	ans += dfs(0, len, 1, 1);
	printf("%lld
", (ans + mod) % mod);
	
}

int main()
{
	int _;
	while(scanf("%d", &_)!=EOF) {
		while(_--) work();
	}

	return 0;
}