As to a permutation p1,p2,⋯,pn from 1 to n, it is uncomplicated for each 1≤i≤n to calculate (l_i,r_i) meeting the condition that min(p_L,p_L+1,⋯,p_R)=p_i if and only if l_i≤L≤i≤R≤r_i for each 1≤L≤R≤n.

Given the positive integers n, (l_i,r_i) (1≤i≤n), you are asked to calculate the number of possible permutations p1,p2,⋯,pn from 1 to n, meeting the above condition.

The answer may be very large, so you only need to give the value of answer modulo 10⁹+7.

The input contains multiple test cases.

For each test case:

The first line contains one positive integer n, satisfying 1≤n≤10⁶.

The second line contains n positive integers l1,l2,⋯,ln, satisfying 1≤li≤i for each 1≤i≤n.

The third line contains n positive integers r1,r2,⋯,rn, satisfying i≤ri≤n for each 1≤i≤n.

It's guaranteed that the sum of n in all test cases is not larger than 3⋅10⁶.

Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.

size_t fread(void *buffer, size_t size, size_t count, FILE *stream); // reads an array of count elements, each one with a size of size bytes, from the stream and stores them in the block of memory specified by buffer; the total number of elements successfully read is returned.

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.