В родном городе Вики, Владивостоке, очень красивое море.
Часто можно видеть ребят, запускающих «блинчики» или «лягушки». Так называется процесс кидания камня в море под небольшим углом, отчего он далеко летит и несколько раз отскакивает от водной глади.
Вика много раз запускала «блинчики» и знает, что если кинуть камень от берега перпендикулярно береговой линии с силой \(f\), то он сперва коснётся воды на расстоянии \(f\) от берега, затем оттолкнётся и вновь коснётся воды на расстоянии \(f - 1\) от предыдущей точки касания. Так камешек будет лететь по прямой, всё сокращая расстояния между точками, в которых он касается воды, пока не упадёт в море.
Формально, точки в которых камень соприкоснётся с водной гладью будут иметь следующие координаты: \(f\), \(f + (f - 1)\), \(f + (f - 1) + (f - 2)\), ... , \(f + (f - 1) + (f - 2) + \ldots + 1\) (если считать, что \(0\) — координата береговой линии).
Как-то раз прогуливаясь вечером по набережной Владивостока, Вика увидела, как группа ребят запускала «блинчики» в море с одной и той же точки с разными силами.
Ей стало интересно, какое максимальное количество ребят могут запустить камешек со своей силой \(f_i\), так чтобы все \(f_i\) были различными целыми положительными числами, и при этом все \(n\) камешков в процессе полёта коснулись воды в точке с координатой \(x\) (если считать, что \(0\) — координата береговой линии).
Немного подумав, Вика ответила на свой вопрос. После этого она начала анализировать, а как будет изменятся ответ на её вопрос, если координату \(x\) домножать на некоторые положительные целые числа \(x_1\), \(x_2\), ... , \(x_q\), выбранные ей для анализа.
Вике сложно справится с таким анализом самостоятельно, поэтому она обратилась к вам за помощью.
Формально, Вику интересует ответ на её вопрос для координат \(X_1 = x \cdot x_1\), \(X_2 = X_1 \cdot x_2\), ... , \(X_q = X_{q-1} \cdot x_q\). Так как ответ для таких координат может быть очень большой, найдите его по модулю \(M\). Гарантируется, что число \(M\) является простым.
Примечание
В первом примере, чтобы камешек коснулся водной глади в точке с координатой \(2\), его нужно кинуть с силой \(2\). Чтобы камешек коснулся воды в точке с координатой \(2 \cdot 3 = 6\), его нужно кинуть с силой \(3\) или с силой \(6\).
Во втором примере можно запустить «блинчик» с силой \(5\) или \(14\), чтобы он коснулся в воды в точке с координатой \(7 \cdot 2 = 14\). Для координаты \(14 \cdot 13 = 182\) есть \(4\) варианта сил — это \(20\), \(29\), \(47\), \(182\).