Time Limit:5000ms Memory Limit:65536KB
Description
John and Brus are training for a card game tournament. During his off-time, Brus
likes to occupy himself with the following game. The game is played with a subset
of a standard deck of 52 distinct cards. Each card can be represented by a
two-character string, where the first character is the rank ('2'-'9', 'T', 'J',
'Q', 'K', or 'A') and the second character is the suit ('S' for Spades, 'C' for
Clubs, 'D' for Diamonds or 'H' for Hearts). All Spades and Clubs are black, and
all Diamonds and Hearts are red. For example, the Jack of Spades is black and is
represented as "JS", and the Nine of Hearts is red and is represented as "9H".
You are given a vector  cards containing the subset of the deck that Brus
is playing with. Each element of cards represents a single card. He wants to
place all of these cards in a line such that every pair of neighboring cards has
the same rank or the same color (or both). Return the number of different ways he
can do this modulo 1234567891.



Input
The first line is a number n which is the number of cards.
The seond line is the card strings seperated bye space.
cards will contain between 1 and 16 elements, inclusive.
Each element of cards will contain exactly two characters, where the first
character is '2'-'9', 'T', 'J', 'Q', 'K' or 'A', and the second character is 'S',
'C', 'D' or 'H'.
All elements of cards will be distinct.


Output
For each test case output the result in a single line.
Sample Input
3
KH QD KC
4
JS JC JD JH
8
2S 3C 4C 5S 6C 7S 8S 9H
9
KD KC AD 7C AH 9C 4H 4S AS

Sample Output
2
24
0
2416
Hint

Source
srm448