I'm practicing programming and I found following problem that I don't know how to solve:
We have 2 sequences A and B that both have length N. We should find number of different ways to permute sequence A such that it is lexicographically smaller than the sequence B.
Sequence (X_1,X_2,...,X_k) is strictly lexicographically smaller then sequence (Y_1,Y_2,...,Y_k), if there exists and index p (1<=p<=k) such that X_p < Y_p and (X_q=Y_q) for all 1 <= q < p
A permutation X of A is considered different form another permutation Y of A if there exists an index i (1<=i<=N) such that X_i != Y_i
For example A(2,2,3,3) has 6 different permutations
1<=N<=100000
1<=A_i<=200000
1<=B_i<=200000
Output should be answer mod 1000000007
I cant find general formula to calculate answer. Can someone please help me?
Thank you all in advance.