宝藏
题号:NC203038
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

    这群海盗们想开始研究深海里的宝藏之谜,结果上来就遇到了一个难题。

    根据线人的线索,深海里的宝藏数正好是满足以下条件的的矩阵数目:

    这个问题对于不学无术的海盗们太难了,他们花重金请你来帮忙计算~你来帮帮他们吧

输入描述:

输入数据包括多组用例,请处理到文件结束。

每组数据一行两个整数,其中表示矩阵的大小,是最终答案的取模。

输出描述:

对于每组用例,一行内输出一个整数,表示矩阵数目。由于答案可能很大,请对取模后输出。
示例1

输入

复制
3 1000000000
100000 1000000000

输出

复制
1
507109376

备注:

保证,输入所有的总和