В Графоляндии вся транспортная сеть представлена в виде неориентированного графа на n вершинах, пронумерованных от 1 до n. В Графоляндии есть k дорог, i-я дорога соединяет ui-ю и vi-ю вершины и имеет покрытие под номером ci.
В Графоляндии существует определение перекрестка. Перекресток — набор из i-й вершины и всех входящих в нее дорог, причем количество дорог должно быть больше 2. Равнозначный перекресток — перекресток, все дороги которого имеют одинаковые покрытия.
Определите количество равнозначных перекрестков в Графоляндии.
Формат входных данных
В первой строке вводятся числа n и k — количество вершин и дорог соответственно (2 ≤ n ≤ 105, 1 ≤ k ≤ 5 * 105).
Далее вводится k строк, в i-й строке вводятся числа ui, vi и ci — вершины, которые соединяет дорога, и вид покрытия дороги (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ ci ≤ 109).
Формат выходных данных
Выведите натуральное число — количество равнозначных перекрестков в Графоляндии.
Настя обожает математику, а сильнее всего Настя любит натуральное число n. Еще у Насти есть q друзей, i-й друг любит натуральное число xi (причем Настя и ее друзья ненавидят число 1, поэтому n, x ≥ 2).
Настя очень добрый человек, поэтому для i-го друга Настя найдет сумму xi + xi2 + ...xin. Также Настя очень ленивый математик, поэтому каждому другу она будет говорить остаток от деления суммы на 109 + 7.
Помогите Насте! Сообщите для каждого друга его остаток от деления суммы!
Формат входных данных
В первой строке вводятся натуральные числа n и q — любимое число Насти и количество друзей Насти соответственно (2 ≤ n ≤ 1018, 1 ≤ q ≤ 105).
Во второй строке вводится q натуральных чисел, i-е число равно xi — любимое число i-го друга (2 ≤ xi ≤ 1018).
Формат выходных данных
Выведите q чисел, где i-е число показывает остаток от деления суммы i-го друга на 109 + 7.
Обратите внимание, что каждое из q чисел лежит на промежутке от 0 до 109 + 6.
На дурацкую олимпиаду по программированию пришло n команд, в каждой команде по 3 человека. Как и на всех дурацких олимпиадах, организаторы решили раздать командам чокопай! У них есть m различных видов чокопая, i-го вида чокопая у организаторов ai штук.
Организаторы хотят раздать чокопай каждой команде таким образом, чтобы никто в команде между собой не поссорился и чтобы каждому участнику команды досталось то же самое множество чокопаев, что и его сокомандникам (более формально, для любого i-го вида у каждого участника команды должно быть одинаковое количество чокопаев i-го вида). Но при этом организаторы не следят за тем, чтобы у каких-либо двух команд был одинаковый набор чокопаек (к примеру, организаторы могут хоть все угощения отдать одной команде и оставить все остальные команды с пустыми руками, могут раздать всем командам чокопай, а могут вообще никому ничего не давать).
Помогите организаторам! Сообщите количество способов раздать чокопай таким образом, чтобы никакие два сокомандника не поссорились между собой.
Формат входных данных
В первой строке вводятся натуральные числа n и m — количество команд и количество видов чокопая (1 ≤ n, m ≤ 105). Во второй строке вводятся последовательность целых чисел ai (0 ≤ ai ≤ 105).
Формат выходных данных
Выведите ответ на задачу по модулю 109 + 7.
Примечание
В первом примере раздать чокопай можно следующими способами:
Первой команде 3 чокопайки 1-го вида и 3 чокопайки 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
Первой команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида;
Первой команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида, второй команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида;
Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 3 чокопайки 1-го вида и 3 чокопайки 2-го вида;
Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
Первой команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
Первой команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида;
Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида.
To conduct a mathematics Olympiad for grades 8 − 11, several classrooms have been allocated. The first classroom contains n rows of desks, with each row having 3 desks. Each desk accommodates exactly one person.
The organizers aim to seat students at all desks in the first classroom in such a way that in any 2 × 2 square of desks, students from different grades sit pairwise (meaning, in any square, there is one student from each of the 8th, 9th, 10th, and 11th grades).
In the illustration, you can see one of the suitable seating arrangements for n = 2 (in both the red and green squares, students from different grades are seated).
How many different ways exist to arrange the participants, given that the total number of students in any grade is greater than the number of desks in the first classroom?
Input format
The only input line contains a natural number n.
Output format
Output a single natural number — the answer to the problem's question modulo 109 + 7 (since the number can be very large).
