Description

传说在剑盾世界⾥有两⼤阵营，分别是守护神剑的剑阵营与掌管神盾的盾阵营。两个阵营都有 n个勇者，每个勇者有⼀个战⽃⼒，同⼀阵营的勇者战⽃⼒互不相同，两个阵营的勇者战⽃⼒差值定义为：$\sum(a_i - b_i)^2$

其中 $a_i$ 表示剑阵营第i个勇者的战⽃⼒，$b_i$ 表示盾阵营第i个勇者的战⽃⼒。

某⽇两阵营相约切磋，每个阵营相邻的两个勇者位置都可以交换，请你通过最⼩次数的交换使两阵营勇者之间的战⽃⼒差值最⼩。如果这个交换数字太⼤，请输出最⼩交换次数对 $10^8-3$ 取模的结果。

Input Format

共三⾏，第⼀⾏包含⼀个整数n，表示双⽅阵营分别拥有的勇⼠数。

第⼆⾏有n个整数，每两个整数之间⽤⼀个空格隔开，表示剑阵营勇⼠的战⽃⼒。

第三⾏有n个整数，每两个整数之间⽤⼀个空格隔开，表示盾阵营勇⼠的战⽃⼒。

数据规模约定： $1≤n≤10^5 ，0≤战⽃⼒≤2^{31}-1$。

Output Format

⼀个整数，表示最少交换次数对108-3取模的结果。

4
1 3 4 2
1 7 2 4​

2