272D.md (1965B)
1 Source: https://codeforces.com/problemset/problem/272/D 2 3 D. Dima and Two Sequences 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Little Dima has two sequences of points with integer coordinates: sequence (*a*1, 1), (*a*2, 2), ..., (*a**n*, *n*) and sequence (*b*1, 1), (*b*2, 2), ..., (*b**n*, *n*). 22 23 Now Dima wants to count the number of distinct sequences of points of length 2·*n* that can be assembled from these sequences, such that the *x*-coordinates of points in the assembled sequence will not decrease. Help him with that. Note that each element of the initial sequences should be used exactly once in the assembled sequence. 24 25 Dima considers two assembled sequences (*p*1, *q*1), (*p*2, *q*2), ..., (*p*2·*n*, *q*2·*n*) and (*x*1, *y*1), (*x*2, *y*2), ..., (*x*2·*n*, *y*2·*n*) distinct, if there is such *i* (1 ≤ *i* ≤ 2·*n*), that (*p**i*, *q**i*) ≠ (*x**i*, *y**i*). 26 27 As the answer can be rather large, print the remainder from dividing the answer by number *m*. 28 29 Input 30 31 The first line contains integer *n* (1 ≤ *n* ≤ 105). The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109). The third line contains *n* integers *b*1, *b*2, ..., *b**n* (1 ≤ *b**i* ≤ 109). The numbers in the lines are separated by spaces. 32 33 The last line contains integer *m* (2 ≤ *m* ≤ 109 + 7). 34 35 Output 36 37 In the single line print the remainder after dividing the answer to the problem by number *m*. 38 39 Examples 40 41 Input 42 43 ``` 44 1 45 1 46 2 47 7 48 ``` 49 50 Output 51 52 ``` 53 1 54 ``` 55 56 Input 57 58 ``` 59 2 60 1 2 61 2 3 62 11 63 ``` 64 65 Output 66 67 ``` 68 2 69 ``` 70 71 Note 72 73 In the first sample you can get only one sequence: (1, 1), (2, 1). 74 75 In the second sample you can get such sequences : (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2). Thus, the answer is 2.