给你两个整数 ， 。然后有一排 台关着的电脑，要考试啦！你需要把这一排电脑都打开，你可以手动打开一台未开启的电脑。每时每刻，如果第 台电脑和第 台电脑都开启了，那么第 台电脑会自动开启 。
你想知道有多少种开启电脑的方案数。两个方案不同当且仅当，你手动开启的电脑集合不同或者手动开启电脑的顺序不同。由于时间有限，你只需要输出方案数对 取模后的结果。
输入一行两个整数 ， 。
样例输入 1
3 100000007
样例输出 1
6
样例输入 2
4 100000007
样例输出 2
20
样例输入 3
400 234567899
样例输出 3
20914007
对于 的数据： 。
对于全部的数据： ，