ACM-ICPC-OJ训练营

问题 L: Limited Permutation

时间限制: 2 Sec 内存限制: 128 MB
提交: 3 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

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

(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.

输入描述

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.

输出描述

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.

样例输入

样例输出

Case #1: 2
Case #2: 3