#include<bits/stdc++.h>
using namespace std;
struct jk{
	char x,y;
}a[20];
string n;
int k;
string ans="0";
bool vis[20];
string sum[100005];
queue<int>q;
string jf(string a,string b){
	string c="";
	int lena=a.size();
	int lenb=b.size();
	if(lena<lenb){
		swap(a,b);
		swap(lena,lenb);
	}
	for(int i=1;i<=lena-lenb;i++){
		b='0'+b;
	}
	int jw=0;
	for(int i=lena-1;i>=0;i--){
		int ans=0;
		ans=a[i]-'0'+b[i]-'0'+jw;
		jw=ans/10;
		c=char(ans%10+'0')+c;
	}
	if(jw){
		c=char(jw+'0')+c;
	}
	return c;
}
void dfs(string op){
	queue<int>q;
	int m=stoi(ans);
	for(int i=1;i<=m;i++){
		if(op==sum[i]){
			return ;
		}
	}
	ans=jf(ans,"1");
	sum[stoi(ans)]=op;
	for(int i=1;i<=k;i++){
		if(!vis[i]){
			for(int j=0;j<op.size();j++){
				if(op[j]==a[i].x){
					op[j]=a[i].y;
					dfs(op);
					op[j]=a[i].x;
				}
			}
		}
	}
	return ;
}
int main(){ 
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>a[i].x>>a[i].y;
	}
	dfs(n);
	cout<<ans;
	return 0;
}

3#4#5#T

dfs做法