Description

【题目背景】 妞妞在公园里游玩时捡到了很多小球，而且每个球都不一样。妞妞找遍了全身只发现了3个一模一样的盒子。她打算把这些小球都装进盒子里（盒子可以为空）。她想知道她总共有多少种放法。

【问题描述】 将N个不同的球放到3个相同的盒子里，求放球的方案总数M。 结果可能很大，我们仅要求输出M mod K的结果。 现在，妞妞已经统计出了N<=10的所有情况。见下表：（表见DOC文档！）

N 1 2 3 4 5 6 7 8 9 10

M 1 2 5 14 41 122 365 1094 3284 9842

Input Format

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

Output Format

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

Sample

【输入样例】

11 10000

【输出样例】

9525

Hint

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