#P18455. Queue Sorting
Queue Sorting
Queue Sorting
题目描述
Burger 最近学习了许多数据结构,她最喜欢的是队列。她想用两个队列实现排序算法。
初始时,队列 和 都为空。对于一个队列,只能进行下列操作:
- 插入:把一个元素放到队尾。
- 弹出:取得并删除队首元素。
需要排序的整数只包含 到 。对于每个 ,整数 总共有 个。记这些整数的总数为
Burger 可以把这 个整数任意排列为一个序列 。当且仅当她能按照以下过程,将所有整数按非降顺序取出时,称 合法:
- 按 中的顺序依次处理每个整数,把它插入两个队列中的任意一个。
- 所有整数都插入完毕后,才开始依次弹出整数。每次可以选择任意一个非空队列,弹出其队首,并将该整数接到结果序列的末尾。最终结果须为非降序列。
她想知道有多少个不同的序列 是合法的。两个序列不同,当且仅当至少存在一个位置,其数值不同;同一个值的不同副本不作区分,同一序列的不同入队方案也不重复计数。
答案可能很大,请对 取模。
输入格式
第一行包含一个整数 ,满足 ,表示整数的种类范围。
第二行包含 个整数 ,满足 。保证
输入只有上述一个实例,没有外层测试数据组数。允许某些数值出现 次,但总数至少为 。
输出格式
输出一行一个整数,表示合法序列数量对 取模的结果。
原样例
4
1 1 1 1
14