Farmer John has N cows (1 ≤ N ≤ 20) with heights a
1…a
N. His barn has N stalls with maximum heights b
1…b
N (so for example b
5=17 means no cows with a height more than 17 can be placed in a stall 5). In how many different ways can the FD place the cows into the stalls so that the height constraint is met for each stall.
Input
The first line contains N. The second line contains N numbers a
1, a
2,…,a
N separated by single spaces. The third line contains N numbers b
1,b
2,…,b
N separated by single spaces. All values are integers in the interval [1,10
9].
Imprint
The number of ways the FD can place cows in the stalls so that the height limit is satisfied for each stall. Note that the answer can be very large, so it requires a 64-bit integer variable such as "long long" in C++.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
1 2 3 4
2 4 3 4
|
8 |
In this example, we cannot place the third cow in the first stall because 3=a3>b1=2. Likewise, we cannot place the 4th cow in the 1st or 3rd stall. One of 8 placement options: Cow 1 to Stall 1, Cow 2 to Stall 2, Cow 3 to Stall 3, Cow 4 to Stall 4. |