#include<bits/stdc++.h>
using namespace std;
#define F(i, l, r) for(auto i = l; i != r; i++)
#define ret return
#define pb push_back
#define cont continue
#define fi0(x) memset((x), 0, sizeof(x))
typedef long long int lint;
const lint mod = 1000000007 ;
int add( int v, int u) {
v + = u;
if ( v >= mod) v - = mod;
ret v;
}
int mul( lint v, lint u) {
ret ( v* u) % mod;
}
class RainbowGraph{
public :
vector< int > col;
bool gr[ 111 ] [ 111 ] ;
int n, m;
int dp[ 10 ] [ 1 << 11 ] [ 11 ] [ 11 ] ;
int ptr;
int revid[ 111 ] ;
int id[ 11 ] [ 11 ] ;
int all_da_ptrs[ 11 ] ;
int ans[ 1 << 11 ] [ 101 ] ;
int countWays( vector< int > c, vector< int > a, vector< int > b) {
n = ( int ) c.size ( ) ;
m = ( int ) a.size ( ) ;
col = c;
fi0( dp) ;
memset ( gr, 0 , sizeof ( gr) ) ;
fi0( ans) ;
F( i, 0 , m) { gr[ a[ i] ] [ b[ i] ] = true ; gr[ b[ i] ] [ a[ i] ] = true ; }
F( cc, 0 , 10 ) {
ptr = 0 ;
F( i, 0 , n) if ( col[ i] == cc) { revid[ i] = ptr; id[ cc] [ ptr++ ] = i; }
all_da_ptrs[ cc] = ptr;
if ( ptr == 0 ) cont;
F( mask, 1 , 1 << ptr) {
F( v, 0 , ptr) {
F( u, 0 , ptr) {
if ( ! ( mask& ( 1 << v) ) ) cont;
if ( ! ( mask& ( 1 << u) ) ) cont;
if ( __builtin_popcount( mask) ! = 1 && v == u) cont;
if ( __builtin_popcount( mask) == 1 ) { dp[ cc] [ mask] [ v] [ u] = 1 ; cont; }
int pmask = mask^ ( 1 << u) ;
F( last, 0 , ptr) {
if ( ! ( pmask& ( 1 << last) ) ) cont;
if ( ! gr[ id[ cc] [ last] ] [ id[ cc] [ u] ] ) cont;
dp[ cc] [ mask] [ v] [ u] = add( dp[ cc] [ mask] [ v] [ u] , dp[ cc] [ pmask] [ v] [ last] ) ;
}
}
}
}
}
F( mask, 1 , 1 << 10 ) {
F( cc, 0 , 10 ) if ( all_da_ptrs[ cc] == 0 && mask& ( 1 << cc) ) cont;
F( last, 0 , n) {
if ( ! ( mask& ( 1 << col[ last] ) ) ) cont;
F( fst, 0 , n) {
if ( col[ fst] ! = col[ last] ) cont;
if ( dp[ col[ last] ] [ ( 1 << all_da_ptrs[ col[ last] ] ) - 1 ] [ revid[ fst] ] [ revid[ last] ] == 0 ) cont;
if ( __builtin_popcount( mask) == 1 ) { ans[ mask] [ last] = add( ans[ mask] [ last] , dp[ col[ last] ] [ ( 1 << all_da_ptrs[ col[ last] ] ) - 1 ] [ revid[ fst] ] [ revid[ last] ] ) ; cont; }
int pmask = mask^ ( 1 << col[ last] ) ;
F( kek, 0 , n) {
if ( ! ( pmask& ( 1 << col[ kek] ) ) || ! gr[ kek] [ fst] ) cont;
ans[ mask] [ last] = add( ans[ mask] [ last] , mul( ans[ pmask] [ kek] , dp[ col[ last] ] [ ( 1 << all_da_ptrs[ col[ last] ] ) - 1 ] [ revid[ fst] ] [ revid[ last] ] ) ) ;
}
}
}
}
int ama = ( 1 << 10 ) - 1 ;
F( cc, 0 , 10 ) if ( all_da_ptrs[ cc] == 0 ) ama ^ = ( 1 << cc) ;
int tot = 0 ;
F( last, 0 , n) tot = add( tot, ans[ ama] [ last] ) ;
ret tot;
}
} ;
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBGKGksIGwsIHIpIGZvcihhdXRvIGkgPSBsOyBpICE9IHI7IGkrKykKI2RlZmluZSByZXQgcmV0dXJuCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgY29udCBjb250aW51ZQojZGVmaW5lIGZpMCh4KSBtZW1zZXQoKHgpLCAwLCBzaXplb2YoeCkpCgp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgbGludDsKY29uc3QgbGludCBtb2QgPSAxMDAwMDAwMDA3OwoKaW50IGFkZChpbnQgdiwgaW50IHUpewoJdiArPSB1OwoJaWYodiA+PSBtb2QpdiAtPSBtb2Q7CglyZXQgdjsKfQoKaW50IG11bChsaW50IHYsIGxpbnQgdSl7CglyZXQgKHYqdSklbW9kOwp9CgpjbGFzcyBSYWluYm93R3JhcGh7CglwdWJsaWM6Cgl2ZWN0b3I8aW50PiBjb2w7Cglib29sIGdyWzExMV1bMTExXTsKCWludCBuLCBtOwoJaW50IGRwWzEwXVsxPDwxMV1bMTFdWzExXTsKCWludCBwdHI7CglpbnQgcmV2aWRbMTExXTsKCWludCBpZFsxMV1bMTFdOwoJaW50IGFsbF9kYV9wdHJzWzExXTsKCWludCBhbnNbMTw8MTFdWzEwMV07CglpbnQgY291bnRXYXlzKHZlY3RvcjxpbnQ+IGMsIHZlY3RvcjxpbnQ+IGEsIHZlY3RvcjxpbnQ+IGIpewoJCW4gPSAoaW50KWMuc2l6ZSgpOwoJCW0gPSAoaW50KWEuc2l6ZSgpOwoJCWNvbCA9IGM7CgkJZmkwKGRwKTsKCQltZW1zZXQoZ3IsIDAsIHNpemVvZihncikpOwoJCWZpMChhbnMpOwoJCUYoaSwgMCwgbSl7Z3JbYVtpXV1bYltpXV0gPSB0cnVlOyBncltiW2ldXVthW2ldXSA9IHRydWU7fQoJCUYoY2MsIDAsIDEwKXsKCQkJcHRyID0gMDsKCQkJRihpLCAwLCBuKWlmKGNvbFtpXSA9PSBjYyl7cmV2aWRbaV0gPSBwdHI7IGlkW2NjXVtwdHIrK10gPSBpO30KCQkJYWxsX2RhX3B0cnNbY2NdID0gcHRyOwoJCQlpZihwdHIgPT0gMCljb250OwoJCQlGKG1hc2ssIDEsIDE8PHB0cil7CgkJCQlGKHYsIDAsIHB0cil7CgkJCQkJRih1LCAwLCBwdHIpewoJCQkJCQlpZighKG1hc2smKDE8PHYpKSljb250OwoJCQkJCQlpZighKG1hc2smKDE8PHUpKSljb250OwoJCQkJCQlpZihfX2J1aWx0aW5fcG9wY291bnQobWFzaykgIT0gMSAmJiB2ID09IHUpY29udDsKCQkJCQkJaWYoX19idWlsdGluX3BvcGNvdW50KG1hc2spPT0xKXtkcFtjY11bbWFza11bdl1bdV0gPSAxOyBjb250O30KCQkJCQkJaW50IHBtYXNrID0gbWFza14oMTw8dSk7CgkJCQkJCUYobGFzdCwgMCwgcHRyKXsKCQkJCQkJCWlmKCEocG1hc2smKDE8PGxhc3QpKSljb250OwoJCQkJCQkJaWYoIWdyW2lkW2NjXVtsYXN0XV1baWRbY2NdW3VdXSljb250OwoJCQkJCQkJZHBbY2NdW21hc2tdW3ZdW3VdID0gYWRkKGRwW2NjXVttYXNrXVt2XVt1XSwgZHBbY2NdW3BtYXNrXVt2XVtsYXN0XSk7CgkJCQkJCX0KCQkJCQl9CgkJCQl9CgkJCX0KCQl9CgkJRihtYXNrLCAxLCAxPDwxMCl7CgkJCUYoY2MsIDAsIDEwKWlmKGFsbF9kYV9wdHJzW2NjXSA9PSAwICYmIG1hc2smKDE8PGNjKSljb250OwoJCQlGKGxhc3QsIDAsIG4pewoJCQkJaWYoIShtYXNrJigxPDxjb2xbbGFzdF0pKSljb250OwoJCQkJRihmc3QsIDAsIG4pewoJCQkJCWlmKGNvbFtmc3RdICE9IGNvbFtsYXN0XSljb250OwoJCQkJCWlmKGRwW2NvbFtsYXN0XV1bKDE8PGFsbF9kYV9wdHJzW2NvbFtsYXN0XV0pLTFdW3JldmlkW2ZzdF1dW3JldmlkW2xhc3RdXSA9PSAwKWNvbnQ7CgkJCQkJaWYoX19idWlsdGluX3BvcGNvdW50KG1hc2spPT0xKXthbnNbbWFza11bbGFzdF0gPSBhZGQoYW5zW21hc2tdW2xhc3RdLCBkcFtjb2xbbGFzdF1dWygxPDxhbGxfZGFfcHRyc1tjb2xbbGFzdF1dKS0xXVtyZXZpZFtmc3RdXVtyZXZpZFtsYXN0XV0pOyBjb250O30KCQkJCQlpbnQgcG1hc2sgPSBtYXNrXigxPDxjb2xbbGFzdF0pOwoJCQkJCUYoa2VrLCAwLCBuKXsKCQkJCQkJaWYoIShwbWFzayYoMTw8Y29sW2tla10pKSB8fCAhZ3Jba2VrXVtmc3RdKWNvbnQ7CgkJCQkJCWFuc1ttYXNrXVtsYXN0XSA9IGFkZChhbnNbbWFza11bbGFzdF0sIG11bChhbnNbcG1hc2tdW2tla10sIGRwW2NvbFtsYXN0XV1bKDE8PGFsbF9kYV9wdHJzW2NvbFtsYXN0XV0pLTFdW3JldmlkW2ZzdF1dW3JldmlkW2xhc3RdXSkpOwoJCQkJCX0JCQkKCQkJCX0KCQkJfQoJCX0KCQlpbnQgYW1hID0gKDE8PDEwKS0xOwoJCUYoY2MsIDAsIDEwKWlmKGFsbF9kYV9wdHJzW2NjXSA9PSAwKWFtYSBePSAoMTw8Y2MpOwoJCWludCB0b3QgPSAwOwoJCUYobGFzdCwgMCwgbil0b3QgPSBhZGQodG90LCBhbnNbYW1hXVtsYXN0XSk7CgkJcmV0IHRvdDsKCX0KfTs=