Головоломка Бессі#11170

Головоломка Бессі

1 секунда

128 мегабайтів

Середня

Фермер Джон і корова Бессі люблять у вільний час обмінюватися математичними головоломками. Остання головоломка, яку ФДж дав Бессі, виявилася доволі складною, і вона не змогла її розв'язати. Тепер Бессі хоче взяти реванш і запропонувати ФДж свою власну складну задачу.

Бессі дає ФДж вираз

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

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

який містить сім змінних $B, E, S, I, G, O$ B, E, S, I, G, O і $M$ (змінна $O$ — це буква " $O$ ", а не цифра нуль).

Для кожної змінної Бессі надає ФДж список, що містить не більше $500$ цілих значень, які може приймати ця змінна. Вона просить ФДж визначити кількість різних способів присвоїти значення змінним так, щоб увесь вираз був кратний $7$ .

Зверніть увагу, що відповідь може не поміщатися у $32$ -бітне ціле число, тому слід використовувати $64$ -бітні цілі числа (наприклад, $l o n g l o n g$ long~long у C або C++).

Вхідні дані

У першому рядку міститься ціле число $n$ . У кожному з наступних $n$ рядків міститься змінна та одне можливе значення для цієї змінної.

Кожна змінна зустрічається у списку принаймні один раз і не більше $500$ разів. Жодне можливе значення не зустрічається більше одного разу для однієї й тієї ж змінної. Усі можливі значення знаходяться в діапазоні від $- 1 0^{5}$ -10^5 до $1 0^{5}$ 10^5.

Вихідні дані

Виведіть одне ціле число — кількість способів, якими ФДж може присвоїти значення змінним так, щоб наведений вище вираз був кратний $7$ .

Приклади

Існують два підхожі присвоєння:

(B, E, S, I, G, O, M) (B, E, S, I, G, O, M) = (2, 5, 7, 9, 1, 16, 19) = (2, 5, 7, 9, 1, 16, 2) \to 51, 765, \to 34, 510.

\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}

Приклад 1