Background

Tim回来了。

Description

Tim在公园里游玩时捡到了很多小球，而且每个球都不一样。Tim找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里（袋子可以为空）。他想知道他总共有多少种放法。
将N个不同的球放到3个相同的袋子里，求放球的方案总数M。
结果可能很大，我们仅要求输出M mod K的结果。
现在，Tim已经统计出了N<=10的所有情况。见下表：

N   1   2   3    4    5   6    7     8     9      10
M   1   2   5   14   41  122  356   1094  3281   9842

Format

Input

两个整数N,K，N表示球的个数。

Output

输出仅包括一行，一个整数M mod K。

Sample 1

Input

11 10000

Output

9525

Limitation

对于 40%数据,10<=N<=10,000
对于100%数据,10<=N<=1,000,000,000
对于 100%数据，K<=100,000.

Source

Amorphophallus Orz Group