Гиперкуб High
N-мерным гиперкубом (или N-кубом) со стороной a > 0 называется фигура в N-мерном евклидовом пространстве, которая строится следующим образом. Выберем в N-мерном пространстве какую-нибудь (N-1)-мерную гиперплоскость. Построим в ней (N-1)-куб. От каждой вершины этого куба проведем отрезок длины a перпендикулярно выбранной плоскости в одном и том же направлении. Концы этих отрезков будут очевидно также лежать в (N-1)-мерной плоскости, параллельной исходной, и образовывать (N-1)-куб. Выпуклая оболочка всех получившихся вершин (и исходного, и нового (N-1)-куба) образует N-мерный гиперкуб. По определению 0-куб – это точка, которая является единственной вершиной этого куба. Нетрудно увидеть, что 1-куб – отрезок на прямой, 2-куб – квадрат на плоскости, 3-куб – обычный трёхмерный куб в трёхмерном пространстве. Гиперкубы большей размерности увидеть несколько сложнее, но тем не менее формально можно построить по определению.
k-мерной гранью (или k-гранью) N-мерного гиперкуба называется такое пересечение его с k-мерной гиперплоскостью, которое не содержит внутренних точек граней большей размерности. Каждый N-куб имеет одну k-грань, совпадающую с ним самим. Можно доказать, что k-грани представляют собой k-кубы. 0-грани – это вершины N-куба, 1-грани – его ребра и т.д.
Требуется вычислить количество k-мерных граней N-мерного гиперкуба.
Входные данные
В единственной строке задаются три целых числа N, k и p (0 ≤ K ≤ N ≤ 10^18, K ≤ 2000, 1 ≤ p ≤ 10^18).
Выходные данные
В единственную строку выведите K+1 число: остаток от деления на p количества 0-граней, 1-граней, ..., K-граней N-куба.