有 个格子，编号为 。初始时所有格子均为白色。
共进行三次染色，第 () 次染色会给定 ，满足 ，然后按照如下规则染色：
三次染色后，求有多少不同的区间 满足 且编号在 内的格子均为白色。由于答案可能较大，你只需要求出答案对 取模后的结果。
从标准输入读入数据。
输入的第一行包含一个正整数 ，表示格子的数量。
输入的第 () 行包含两个非负整数 ，表示第 次染色给定的参数。
输出到标准输出。
输出一行一个非负整数表示满足条件的区间数量对 取模后的结果。
10 5 3 7 0 7 1
8
1000000 114514 114 114514 810 200000 5
136032633
对于所有测试数据，均有：
对于每个子任务：
