一个序列的重排列是指对这个序列中的元素进行若干次（包括0次）交换操作后得到的新序列

在本题中，序列中可能出现重复的数字，他们被视作不同的元素

例如，序列1 1的重排列有两种

现在有两个长度为 N 的非负整数序列 A 和 B，问有多少种 A 的重排列满足对于所有的 1≤i≤N，有Ai≤Bi

由于答案可能很大，你只需要输出答案对1e9+7取模的结果

输入描述:


 

输入第一行，包含一个正整数 N

接下来一行，N 个非负整数表示序列 A

再接下来一行，N 个非负整数表示序列 B

1≤N≤100,000,0≤Ai,Bi≤109

输出描述:


 

一行一个整数，表示答案

示例1

输入

复制

4
1 1 2 3
1 2 3 4

输出

复制

8

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,s,l;
int a[1000001],b[1000001];
long long mod=1e9+7;
int main() 
{
    cin>>n;
    for(int i=1; i<=n;i++)
	cin>>a[i];
    for(int i=1;i<=n;i++)
	cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    s=1;
    l=0;
    for(int i=n;i>=1;i--)
    {
    	int x=a[i];
    	k=n-(lower_bound(b+1,b+1+n,x)-b)+1;
    	s*=(k-l)%mod;
    	s%=mod;
    	l++;
    }
    cout<<s<<endl;
   	
}