Bessie Goes Moo#11170
Sign in

Bessie Goes Moo

1 second
128 megabytes
Medium

Farmer John and Bessie the cow enjoy exchanging math puzzles in their free time. The last puzzle FJ gave Bessie was quite difficult, and she was unable to solve it. Now she wants to get even with FJ by giving him a challenging puzzle of her own.

Bessie gives FJ the expression

(B + E + S + S + I + E)(G + O + E + S)(M + O + O),

which contains the seven variables B, E, S, I, G, O, and (the variable is the letter '', not the digit zero).

For each variable, she gives FJ a list of up to integer values that the variable may take. She asks FJ to count the number of different ways to assign values to the variables such that the entire expression is a multiple of .

Note that the answer can be too large to fit in a -bit integer, so you should use -bit integers (such as long~long in C or C++).

Input

The first line contains an integer . Each of the next lines contains a variable and a possible value for that variable.

Each variable appears in the list at least once and at most times. No possible value is listed more than once for the same variable. All possible values are in the range -10^5 to 10^5.

Output

Print one integer, representing the number of ways FJ can assign values to the variables such that the expression above is a multiple of .

Examples

The two possible assignments are

\begin{aligned} (B,E,S,I,G,O,M) &= (2,5,7,9,1,16,19) &&\rightarrow 51{,}765,\\ (B,E,S,I,G,O,M) &= (2,5,7,9,1,16,2) &&\rightarrow 34{,}510. \end{aligned}

Example 1

Loading
Loading