你和他曾一起尝试过解决一道题目。
一道题目的解决方案可以看作从 到 编号的 个性质。每个性质都可以通过一个特点 来代表， 越大说明这个性质越智力， 越小表示这个性质越套路。由于每个性质都不完全相同，因此 组成了一个长度为 的排列。
他是日本题领域大神。他经过思考想出了 个性质，这 个性质组成的子序列 恰好是 的所有长度为 的子序列中字典序最大的那个。
你是中国题领域大神。你经过思考也想出了 个性质，这 个性质组成的子序列 恰好是 的所有长度为 的子序列中字典序最小的那个。
你们把你们思考出的性质分别罗列。你们在一张纸条上记录下了 和 之间的某一个最长公共子序列。
这时下课铃响了，你们一起去吃饭了。
后来过去了好久啊，你们也早已分道扬镳。在某一天，你在整理物品的时候又发现了这张纸条。你又想起了这道没能解决的难题。你想知道，当年的那道题目，有多少种可能的解决方案，最终可能会导致这张纸条的出现。
答案对 取模。