Problem Description

As to a permutation 

p1,p2,⋯,pn from 1 to n, it is uncomplicated for each 1≤i≤n to calculate (li,ri) meeting the condition that min(pL,pL+1,⋯,pR)=pi if and only if li≤L≤i≤R≤ri for each 1≤L≤R≤n.

Given the positive integers n, (li,ri) (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 109+7.

 

 

Input

The input contains multiple test cases.

For each test case:

The first line contains one positive integer 

n, satisfying 1≤n≤106.

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⋅106.

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.

 

 

Output

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.

 

 

Sample Input

3

1 1 3

1 3 3

5

1 2 2 4 5

5 2 5 5 5

 

 

Sample Output

Case #1: 2 

Case #2: 3

 

题意：对于一个由1~n组成的排列称为合法的，必须满足这样的条件： 有n个（li，ri），对于每个 i 必须满足  min(pL,pL+1,⋯,pR)=pi if and only if li≤L≤i≤R≤ri for each 1≤L≤R≤n.

           现在给了n个(li,ri)求满足的排列有多少个。

 

思路：对于每个（li，ri）,a[li-1]<a[i]>a[ri+1] ,并且a[i]是a[li]~a[ri]的最小值，那么可以想到：对于区间(1,n)一定有一个最小值，所以一定有一个区间是(1,n)(用X表示)，那么这个最小值把区间X分成两部分U和V ，所以一定存在为U和V的区间，如果不存在，那么输出0，令f(X)表示符合条件的区间X的排列数，那么f(X)=f(U)*f(V)*C(U+V+1,U)   【注：C()表示组合数，U 表示区间U的大小】，所以我们只需要从区间(1,n)进行深搜即可，其中因为数据太大取模会用到逆元和组合数。

 

代码如下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long LL;const int N=1e6+5;const LL mod=1e9+7;LL fac[N], Inv[N];/*int Scan()///输入外挂{    int res=0,ch,flag=0;    if((ch=getchar())=='-')        flag=1;    else if(ch>='0'&&ch<='9')        res=ch-'0';    while((ch=getchar())>='0'&&ch<='9')        res=res*10+ch-'0';    return flag?-res:res;}*/namespace IO {    const int MX = 4e7; //1e7占用内存11000kb    char buf[MX]; int c, sz;    void begin() {        c = 0;        sz = fread(buf, 1, MX, stdin);    }    inline bool read(int &t) {        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;        if(c >= sz) return false;        bool flag = 0; if(buf[c] == '-') flag = 1, c++;        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';        if(flag) t = -t;        return true;    }}void Init(){    fac[0] = Inv[0] = fac[1] = Inv[1] = 1;    for(int i=2; i
           
            s2.r; return s1.l