# Berenice P98733

Statement

html

He whispered me of a violated grave—of a disfigured body enshrouded, yet still breathing—still palpitating—still alive!…With a shriek I bounded to the table, and grasped the box that lay upon it. But I could not force it open; and in my tremor, it slipped from my hands, and fell heavily, and burst into pieces; and from it, with a rattling sound, there rolled out some instruments of dental surgery, intermingled with thirty-two small, white and ivory-looking substances that were scattered to and fro about the floor.

Egaeus has just returned to Berenice her thirty-two precious teeth. Berenice is trying to put them in order, but she is confused (which is strange, since she only suffered an epilepsy attack, was considered dead and consequently was buried alive, and was awakened from her dream inside a grave by her beloved cousin Egaeus uprooting all her teeth). However, despite his monomania and before plucking all the teeth, Egaeus was cautious enough to label each tooth with a number. He observed that the upper line of teeth was sorted in strictly decreasing order. So was the lower line of teeth. Additionally, each tooth in the upper line had a label strictly larger than the corresponding label below.

Help poor Berenice to put her teeth in order, or at least tell her how many combinations are consistent with the labels so gently put by her dear cousin Egaeus. Assume that two or more teeth labelled with the same number are indistinguishable.

Input

Input has several cases. Every case consists of the number of teeth n of the upper line and of the lower line, followed by 2n integers between −109 and 109. Assume 1 ≤ n ≤ 1000.

Output

For every case, print its number, followed by the number of valid combinations, which will be at most 1018 for the given cases. Afterwards, if there is exactly one valid combination, print it in two lines.

Public test cases
• Input

```1   9 10
4   2 5 3 5 8 5 9 5
2   -1 0 0 1
2   1000000 7000000 3000000 5000000
5   8 4 6 7 5 4 10 6 3 7
22
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38 39 40 41 42 43 44
```

Output

```Case #1: 1
10
9
Case #2: 0
Case #3: 1
1 0
0 -1
Case #4: 2
Case #5: 1
10 8 7 6 4
7 6 5 4 3
Case #6: 91482563640
```
• Information
Author
Salvador Roura
Language
English
Official solutions
C++
User solutions
C++