题目描述
球球有 个一次函数，其中第 个一次函数为 。聪明的她发现，两个一次函数的复合 仍然是一次函数：
现在有一个正整数 ，请帮助球球重新排列这些一次函数，使得它们依次复合后代入 的值最大。
也就是说：你需要寻找一个长为 的排列 ，使得 的值最大。
由于答案可能很大，你只需要输出结果对 取模的值。
输入格式
从标准输入读入数据。
输入的第一行有两个空格分隔的正整数 。
接下来 行，每行两个空格分隔的整数 。
输出格式
输出到标准输出。
输出一行一个整数表示答案。
样例1输入
样例1输出
样例2
见题目目录下的 2.in 与 2.ans。
子任务
对于 的测试数据，有 。
对于 的测试数据，有 。
对于 的测试数据，有 。
对于另外 的测试数据，有 。
对于 的测试数据，保证 ，，，。