Проблема Миколая

Миколаю потрібно розвести подарунки для n (n ≤ 10^18) дітей. Його цікавить скількома способами він може це зробити. Вам потрібно дати відповідь на це просте питання. Оскільки ця кількість може бути дуже великою, виведіть результат за модулем m (m ≤ 2009).

Вхідні дані

В одному рядку задано два натуральні числа n та m.

Вихідні дані

Єдине число - шукана кількість.

Приклади