#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;
typedef long long LL;
typedef double ld;
typedef unsigned int Int;
const int MAX=40;
const int NUM=10;
const int COLOR=3;
const int P=31;
LL Pow[MAX];
int n;
int num[NUM][COLOR];
//1-2
//2-3
//3-1
//1-1
//2-2
//3-3
const int lll[]={0,1,0,0,1,2};
const int rrr[]={1,2,2,0,1,2};
int g[3][3]=
{
{3,0,2},
{0,4,1},
{2,1,5}
};
const int Mod=3000007;
int tot;
int hash[Mod],next[Mod];
LL q[Mod];
int find(LL a)
{
LL u=a% Mod;
int i;
for(i=hash[u];i;i=next[i])
if(q[i]==a)
return i;
++tot;
next[tot]=hash[u];
hash[u]=tot;
q[tot]=a;
return tot;
}
void dfs(int u,int num,LL now)
{
if(u==-1)
{
find(now);
return;
}
int i;
REP(i,0,num)
dfs(u-1,num-i,now*P+i);
return;
}
LL get(LL u,int b)
{
return u/Pow[b]%P;
}
const int MAXS=1947792+10;
bool Hash[MAXS][3];
Int cc[MAXS][3];
Int solve(int d,int s)
{
if(Hash[d][s])
return cc[d][s];
if(q[d]==0)
return 1;
Hash[d][s]=1;
cc[d][s]=0;
LL p=q[d];
int j;
REP2(j,0,3)
if(get(p,g[s][j]))
cc[d][s]+=get(p,g[s][j])*solve(find(p-Pow[ g[s][j] ]),j);
return cc[d][s];
}
int nowF=0,lastF=1;
Int f[2][MAXS];
map<LL,Int> F;
int used[NUM],color[NUM],top;
void dfs2(LL have,int now,vector<int> q)
{
int i,j;
REP2(i,0,top)
if(!used[i])
break;
if(i==top && !q.size())
{
F[have]++;
return;
}
REP2(j,0,top)
if(used[j]==now)
break;
if(i>j && q.size() && q[0]<=q[q.size()-1])
dfs2(have+Pow[g[q[0]][q[q.size()-1]]],now+1,vector<int>());
REP2(j,0,top)
if(!used[j] && (q.size()==0 || q[q.size()-1]!=color[j]))
{
used[j]=now;
vector<int> tmp=q;
tmp.pb(color[j]);
dfs2(have,now,tmp);
used[j]=0;
}
}
void work(int number)//不能有相同颜色的连接在一起。。所以得暴力搜索了
{
int i,j;
memset(used,0,sizeof used);
top=0;
REP2(i,0,3)
REP2(j,0,num[number][i])
color[top++]=i;
memset(used,0,sizeof used);
F.clear();
dfs2(0,1,vector<int>());
swap(nowF,lastF);
memset(f[nowF],0,sizeof f[nowF]);
REP(j,1,tot)
if(f[lastF][j])
for(map<LL,Int>::iterator it=F.begin();it!=F.end();++it)
f[nowF][find(q[j]+it->x)]+=f[lastF][j]*it->y;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j;
Pow[0]=1;
REP2(i,1,MAX)
Pow[i]=Pow[i-1]*P;
scanf("%d",&n);
REP(i,1,n)
{
int a,b;
scanf("%d%d",&a,&b);
num[b][a]++;
}
memset(q,-1,sizeof q);
tot=0;
dfs(5,n,0);
f[nowF][find(0)]=1;
REP2(i,0,10)
work(i);
Int ans=0;
REP(i,1,tot)
if(f[nowF][i])
REP2(j,0,3)
ans+=f[nowF][i]*solve(i,j);
cout<<ans<<endl;
return 0;
}
I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxjc3RkbGliPgojaW5jbHVkZTxjc3RyaW5nPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxmc3RyZWFtPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPGN0aW1lPgojaW5jbHVkZTxzZXQ+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxjbWF0aD4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxiaXRzZXQ+CiNpbmNsdWRlPGZ1bmN0aW9uYWw+CiNkZWZpbmUgeCBmaXJzdAojZGVmaW5lIHkgc2Vjb25kCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgUkVQKGksbCxyKSBmb3IoKGkpPShsKTsoaSk8PShyKTsrKyhpKSkKI2RlZmluZSBSRVAyKGksbCxyKSBmb3IoKGkpPShsKTsoaSkhPShyKTsrKyhpKSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgbG9uZyBsb25nIExMOwp0eXBlZGVmIGRvdWJsZSBsZDsKdHlwZWRlZiB1bnNpZ25lZCBpbnQgSW50OwoKY29uc3QgaW50IE1BWD00MDsKY29uc3QgaW50IE5VTT0xMDsKY29uc3QgaW50IENPTE9SPTM7CmNvbnN0IGludCBQPTMxOwpMTCBQb3dbTUFYXTsKCmludCBuOwppbnQgbnVtW05VTV1bQ09MT1JdOwoKLy8xLTIKLy8yLTMKLy8zLTEKLy8xLTEKLy8yLTIKLy8zLTMKY29uc3QgaW50IGxsbFtdPXswLDEsMCwwLDEsMn07CmNvbnN0IGludCBycnJbXT17MSwyLDIsMCwxLDJ9OwoKaW50IGdbM11bM109CnsKCXszLDAsMn0sCgl7MCw0LDF9LAoJezIsMSw1fQp9OwoKY29uc3QgaW50IE1vZD0zMDAwMDA3OwppbnQgdG90OwppbnQgaGFzaFtNb2RdLG5leHRbTW9kXTsKTEwgcVtNb2RdOwoKaW50IGZpbmQoTEwgYSkKewogICAgTEwgdT1hJSBNb2Q7CiAgICBpbnQgaTsKICAgIGZvcihpPWhhc2hbdV07aTtpPW5leHRbaV0pCiAgICAgICAgaWYocVtpXT09YSkKICAgICAgICAgICAgcmV0dXJuIGk7CgkrK3RvdDsKICAgIG5leHRbdG90XT1oYXNoW3VdOwogICAgaGFzaFt1XT10b3Q7CiAgICBxW3RvdF09YTsKICAgIHJldHVybiB0b3Q7Cn0KCnZvaWQgZGZzKGludCB1LGludCBudW0sTEwgbm93KQp7CglpZih1PT0tMSkKCXsKCQlmaW5kKG5vdyk7CgkJcmV0dXJuOwoJfQoJaW50IGk7CglSRVAoaSwwLG51bSkKCQlkZnModS0xLG51bS1pLG5vdypQK2kpOwoJcmV0dXJuOwp9CgpMTCBnZXQoTEwgdSxpbnQgYikKewoJcmV0dXJuIHUvUG93W2JdJVA7Cn0KCmNvbnN0IGludCBNQVhTPTE5NDc3OTIrMTA7Cgpib29sIEhhc2hbTUFYU11bM107CkludCBjY1tNQVhTXVszXTsKCkludCBzb2x2ZShpbnQgZCxpbnQgcykKewoJaWYoSGFzaFtkXVtzXSkKCQlyZXR1cm4gY2NbZF1bc107CglpZihxW2RdPT0wKQoJCXJldHVybiAxOwoJSGFzaFtkXVtzXT0xOwoJY2NbZF1bc109MDsKCUxMIHA9cVtkXTsKCWludCBqOwoJUkVQMihqLDAsMykKCQlpZihnZXQocCxnW3NdW2pdKSkKCQkJY2NbZF1bc10rPWdldChwLGdbc11bal0pKnNvbHZlKGZpbmQocC1Qb3dbIGdbc11bal0gXSksaik7CglyZXR1cm4gY2NbZF1bc107Cn0KCmludCBub3dGPTAsbGFzdEY9MTsKSW50IGZbMl1bTUFYU107CgptYXA8TEwsSW50PiBGOwoKaW50IHVzZWRbTlVNXSxjb2xvcltOVU1dLHRvcDsKCnZvaWQgZGZzMihMTCBoYXZlLGludCBub3csdmVjdG9yPGludD4gcSkKewoJaW50IGksajsKCVJFUDIoaSwwLHRvcCkKCQlpZighdXNlZFtpXSkKCQkJYnJlYWs7CglpZihpPT10b3AgJiYgIXEuc2l6ZSgpKQoJewoJCUZbaGF2ZV0rKzsKCQlyZXR1cm47Cgl9CglSRVAyKGosMCx0b3ApCgkJaWYodXNlZFtqXT09bm93KQoJCQlicmVhazsKCWlmKGk+aiAmJiBxLnNpemUoKSAmJiBxWzBdPD1xW3Euc2l6ZSgpLTFdKQoJCWRmczIoaGF2ZStQb3dbZ1txWzBdXVtxW3Euc2l6ZSgpLTFdXV0sbm93KzEsdmVjdG9yPGludD4oKSk7CglSRVAyKGosMCx0b3ApCgkJaWYoIXVzZWRbal0gJiYgKHEuc2l6ZSgpPT0wIHx8IHFbcS5zaXplKCktMV0hPWNvbG9yW2pdKSkKCQl7CgkJCXVzZWRbal09bm93OwoJCQl2ZWN0b3I8aW50PiB0bXA9cTsKCQkJdG1wLnBiKGNvbG9yW2pdKTsKCQkJZGZzMihoYXZlLG5vdyx0bXApOwoJCQl1c2VkW2pdPTA7CgkJfQp9Cgp2b2lkIHdvcmsoaW50IG51bWJlcikvL+S4jeiDveacieebuOWQjOminOiJsueahOi/nuaOpeWcqOS4gOi1t+OAguOAguaJgOS7peW+l+aatOWKm+aQnOe0ouS6hgp7CglpbnQgaSxqOwoJbWVtc2V0KHVzZWQsMCxzaXplb2YgdXNlZCk7Cgl0b3A9MDsKCVJFUDIoaSwwLDMpCgkJUkVQMihqLDAsbnVtW251bWJlcl1baV0pCgkJCWNvbG9yW3RvcCsrXT1pOwoKCW1lbXNldCh1c2VkLDAsc2l6ZW9mIHVzZWQpOwoJRi5jbGVhcigpOwoJZGZzMigwLDEsdmVjdG9yPGludD4oKSk7CgoJc3dhcChub3dGLGxhc3RGKTsKCW1lbXNldChmW25vd0ZdLDAsc2l6ZW9mIGZbbm93Rl0pOwoKCVJFUChqLDEsdG90KQoJCWlmKGZbbGFzdEZdW2pdKQoJCQlmb3IobWFwPExMLEludD46Oml0ZXJhdG9yIGl0PUYuYmVnaW4oKTtpdCE9Ri5lbmQoKTsrK2l0KQoJCQkJZltub3dGXVtmaW5kKHFbal0raXQtPngpXSs9ZltsYXN0Rl1bal0qaXQtPnk7Cn0KCmludCBtYWluKCkKewojaWZuZGVmIE9OTElORV9KVURHRQoJZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pO2ZyZW9wZW4oIm91dHB1dC50eHQiLCJ3IixzdGRvdXQpOwojZW5kaWYKCWludCBpLGo7CgoJUG93WzBdPTE7CglSRVAyKGksMSxNQVgpCgkJUG93W2ldPVBvd1tpLTFdKlA7CgoJc2NhbmYoIiVkIiwmbik7CglSRVAoaSwxLG4pCgl7CgkJaW50IGEsYjsKCQlzY2FuZigiJWQlZCIsJmEsJmIpOwoJCW51bVtiXVthXSsrOwoJfQoKCW1lbXNldChxLC0xLHNpemVvZiBxKTsKCXRvdD0wOwoKCWRmcyg1LG4sMCk7CgoJZltub3dGXVtmaW5kKDApXT0xOwoJUkVQMihpLDAsMTApCgkJd29yayhpKTsKCglJbnQgYW5zPTA7CglSRVAoaSwxLHRvdCkKCQlpZihmW25vd0ZdW2ldKQoJCQlSRVAyKGosMCwzKQoJCQkJYW5zKz1mW25vd0ZdW2ldKnNvbHZlKGksaik7Cgljb3V0PDxhbnM8PGVuZGw7CglyZXR1cm4gMDsKfQo=