X 正在编写她的小说，她需要为这本小说设定一条世界线，也就是各个事件发生的时间次序。
X 已经想好了 个事件，第 个事件有一个 到 内的类型 。X 要将这 个事件的类型排成一个序列 。
X 希望小说的内容跌宕起伏，所以对于 的每个前缀 ， 必须是该前缀的最大值或最小值。
X 想要知道，符合要求的本质不同的序列 共有多少种？
由于数量实在是太大了，X 让你将答案对 取模。
本质不同：定义两个长度为 的序列 和 是本质不同的，当且仅当存在 ，使得 。
第一行一个正整数 ，表示事件的个数。
第二行 个正整数，第 个正整数为 。
一行一个正整数，表示答案对 取模后的值。
3 1 3 2
4
8 3 7 1 7 4 2 5 1
126
对于样例 1，一共有以下四种序列是符合要求的：
本题采用捆绑测试。
对于所有测试数据，，。
