НачалоПодразделы
Другие разделы
| 1742. Премии |
| 1743. Прямоугольники |
| 1744. Chess |
| 1745. Деление |
| 1747. Огонь! |
| 1748. Хомяки |
| 1749. Holidays |
Дата и время
20/12/2024 23:19:41
1746. Оценка
Оценка
Производящие функции и матричное представлениеОлимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 3E) |
| 27/06/2012 | Лето 2012 - 3 (E) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вася очень любит программировать. Еще он очень любит научную фантастику.
Как-то на каникулах, начитавшись книжек со своим другом Петей, Вася решил вывести формулу,
показывающую рост популяции на Марсе. По прикидкам Васи после `N` лет жизни планеты популяция марсиан
должна составлять `S_N` марсиан, где `S_N` определяется по формуле:
`S_N\ =\ sum_{k=0}^{N-1}\ k^2*2^k`
Петя, после того как Вася рассказал ему свою теорию, засомневался и решил
вычислить это число на компьютере, чтобы убедиться в его достоверности. К тому же, Петя
недавно прочитал умную книжку по программированию, поэтому он думает, что это не займет много времени.
Вам предлагается сделать то же самое, но без чтения умной книжки. Заметьте, что для Вашего удобства
необходимо вывести `S_N` по модулю `M`.
Первая строка входа содержит количество тестов. Для каждого теста в
отдельной строке содержится число `N` – возраст планеты Марс и число `M` – модуль. `0\ <\ N\ ≤\ 1000000000`,
`0\ <\ M\ ≤\ 1000000000`.
Для каждого теста в выходной файл выводится строка, содержащая ожидаемое число марсиан после `N` лет жизни планеты по модулю `M`.
Пример ввода
2 1 1000 2 1000
Пример вывода
0 2
