#P12394. 「RiOI-6」神曲
「RiOI-6」神曲
题目背景
安慰一个伤心的人,真的好困难呢……
在好友最需要自己的时候,明明有很多话可说,却只会“好惨”“拍拍”“抱抱”什么的,真的很让人自责啊。
如果萝卜能让所有人对感情认真起来,像她这样被伤害的人,是不是就会少一些呢?
题目描述
定义一个长度为 ,值域为 的二元组序列 是好的,当且仅当:
- 。
- $\forall 1\le i<j\le n, (l_j\le l_i\le r_i\le r_j)\lor(r_j < l_i)\lor(r_i < l_j)$。
换句话说,每个二元组代表一个区间,且对于所有 ,要么 被 包含,要么 与 没有交集。
给定 。请对 ,求出有多少个长度为 ,值域为 的二元组序列是好的。答案对 取模。
输入格式
一行两个正整数 。
输出格式
一行 个非负整数,表示答案。
1 5
1 3 6 10 15
2 2
1 7
10 20
1 2047 261625 10391745 210766920 738437852 751995961 367882293 626598267 990684424 32946479 746153195 309367626 577393442 149727732 683395486 756615148 203162153 948422841 561114284
100 20
1 766755082 570047877 716144748 321097835 123137643 571618454 644127872 879655648 371687313 984928153 761377418 790560387 887056207 799077157 156396768 647907515 242209960 978001146 356334941
提示
【样例解释】
对于样例 ,满足在值域内的区间显然有 种。所以 时答案为 。
对于样例 :
当 时,显然只有一种好的序列:。
当 时:好的序列有以下 种:
- 。
- 。
- 。
- 。
- 。
- 。
- 。
对于样例 ,暂时不能给你一个明确的答复。
【数据范围】
本题开启捆绑测试。
子任务 | 分数 | ||
---|---|---|---|
对于 的数据,。
请注意常数因子对程序运行效率的影响。