<PREV Problem:
NEXT>
Solved by 93 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Catalan numbers

Time limit = 3 second(s)

C(N) — Catalan number.

See Wikipedia Article "Catalan numbers" .

Find C(N) % K (operator % stands for residual).

Input. One line with N and K.

1 ≤ N ≤ 500 000, 1 ≤ K ≤ 2 000 000 000.

Output. C(N) % K.

Input#1
3 8		
Output#1
5

Input#2
1 352745736	
Output#2
1

Input#3
2 7344		
Output#3
2

Input#4
10000 1024
Output#4
480

Input#5
23 22	
Output#5
6

Author:
Artem Voroztsov -- statement and tests, Vyacheslav Bykov -- solution.

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.162.181.75