← 返回题目列表

AtCoder · cf16_exhibition_final_a

A. 一维匹配

中文机器翻译题面 查看原题

分数: 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