分数: 500 点
问题陈述
有 N 计算机和 N 一维世界中的套接字。 的坐标 i第计算机是 a_i,以及 i-th 套接字是 b_i。 可以保证这些 2N 坐标是两两不同的。
Snuke 希望使用电缆将每台计算机连接到插座。 每个插座只能连接一台计算机。
有多少种方法可以最小化电缆的总长度? 计算答案的模数 10^9+7.
约束
- 1 ≤ N ≤ 10^5
- 0 ≤ a_i, b_i ≤ 10^9
- 坐标是整数。
- 坐标是两两不同的。
输入
输入由标准输入按以下格式给出:
N a_1 : a_N b_1 : b_N
输出
打印最小化电缆总长度的方法数,模数 10^9+7.
示例输入 1
2 0 10 20 30
示例输出 1
2
有两种最佳连接: 0-20, 10-30 和 0-30, 10-20。 在这两种连接中,电缆的总长度为 40.
示例输入 2
3 3 10 8 7 12 5
示例输出 2
1