Гіперкуб 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-куба.