Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Nicholas must deliver gifts to n (n ≤ `10^18`

) children. He wonders in how many ways he can do it. You need to answer this simple question. Since this number may be very large, print the result modulo m (m ≤ 2009).

Two positive integers n and m.

Print the number of possible ways deliver presents.

Input #1

Answer #1

Input #2

Answer #2