Statistics

Problem Statement for "CircuitDesign"

Problem Statement

A given circuit part is made of two rows of cells with a space in between them. Some of the cells of the top row need to be connected with some other cells of the bottom row with wires. A connection can be described as a pair of integers (x,y), which means that cell x of the top row needs to be connected with cell y of the bottom row.

The following picture illustrates an arrangement with the connections (1,1) (1,2) (2,2) (4,2) (4,3). 

+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+
  |\  |    __/|
  | \ | __/ _/
  |  \|/   /
+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+

Wires have to be printed in a 2-dimensional space and cannot cross each other, so if cell x1 of the top row needs to be connected to cell y1 of the bottom row and cell x2 of the top row needs to be connected with cell y2 of the bottom row, the following must hold:

  • (x1<=x2 and y1<=y2) or (x1>=x2 and y1>=y2).

Fortunately, the scientists noted that they may exchange cells placed on the same row. For instance, the following list of connections would not be valid according to the above rule: (1,2) (2,1). But, if they place the top row in the regular order [1,2] and the bottom row in reverse order [2,1], then no wires cross and the arrangement is valid. Moreover, they could also achieve that by placing the top row in reverse order and the bottom row in regular order. The following picture illustrates the situation: 

+---+---+            +---+---+            +---+---+
| 1 | 2 |            | 1 | 2 |            | 2 | 1 |
+---+---+            +---+---+            +---+---+
  \  /                 |   |                |   |
   \/      _____\      |   |                |   |
   /\           /      |   |       or       |   |
  /  \                 |   |                |   |
+---+---+            +---+---+            +---+---+
| 1 | 2 |            | 2 | 1 |            | 1 | 2 |
+---+---+            +---+---+            +---+---+

You will be given an int n that represents the number of cells in each row, and the list of connections as two int[]s top and bottom. For each i, the pair (top[i],bottom[i]) is a required connection. Return the number of possible arrangements of the cells in each row that result in no wires crossing, modulo 1000000007. Two arrangements are different if any cell in any row has a different placement. See examples for further clarification.

Definition

Class:
CircuitDesign
Method:
countPerms
Parameters:
int, int[], int[]
Returns:
int
Method signature:
int countPerms(int n, int[] top, int[] bottom)
(be sure your method is public)

Constraints

  • n will be between 1 and 50, inclusive.
  • top will contain between 1 and 50 elements, inclusive.
  • top and bottom will contain the same number of elements.
  • Each element of top and bottom will be between 1 and n, inclusive.
  • Each pair (top[i] , bottom[i]) will be different.

Examples

  1. 4

    {1,1,2,4,4}

    {1,2,2,2,3}

    Returns: 32

    This is the first example drawn in the problem statement.

  2. 2

    {1,2}

    {2,1}

    Returns: 2

    The second example drawn in the problem statement.

  3. 3

    {1,1,1,2,2,2,3,3,3}

    {1,2,3,1,2,3,1,2,3}

    Returns: 0

    There are too many wires to avoid crossing.

  4. 30

    {5,5,5,5,5,5,5,5,5, 5,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}

    {1,2,3,4,5,6,7,8,9,10,15,15,15,15,15,15,15,15,15,15,25,25,25,25,25,25,25,25,25,25}

    Returns: 628573100

  5. 5

    {1,2,3,4,5,1,2,3,4}

    {1,2,3,4,5,5,1,4,2}

    Returns: 2

  6. 5

    {1,2,3,4,5,1,2,3,4,1}

    {1,2,3,4,5,2,3,4,5,5}

    Returns: 0

  7. 4

    {1,1,1,2,3,4}

    {1,2,3,1,2,3}

    Returns: 0

  8. 50

    {1}

    {1}

    Returns: 539792695

  9. 2

    {1,1,2,2}

    {1,2,1,2}

    Returns: 0

  10. 1

    {1}

    {1}

    Returns: 1

  11. 3

    {1,2,3,1,2}

    {2,1,2,3,3}

    Returns: 2

  12. 10

    {4,7,7,8,8,9,9,2,2,10,10,3,3,1,1,6,6,5,5}

    {4,4,7,7,8,8,9,9,2,2,10,10,3,3,1,1,6,6,5}

    Returns: 2

  13. 25

    {14,7,7,11,11,1,1,10,10,24,24,2,2,13,13,20,20,6,6,22,22,3,3,19,19,4,4,16,16,18,18,23,23,25,25,17,17,9,9,15,15,12,12,21,21,5,5,8,8}

    {14,14,7,7,11,11,1,1,10,10,24,24,2,2,13,13,20,20,6,6,22,22,3,3,19,19,4,4,16,16,18,18,23,23,25,25,17,17,9,9,15,15,12,12,21,21,5,5,8}

    Returns: 2

  14. 10

    {10,5,7,7,7,3,1,1,1,6,8,8,8,2,9,9,9,4}

    {10,10,10,5,7,7,7,3,1,1,1,6,8,8,8,2,9,9}

    Returns: 40

  15. 25

    {21,21,21,24,24,24,1,7,7,7,20,15,15,15,17,22,22,22,12,8,8,8,13,9,9,9,6,11,11,11,5,10,10,10,16,19,19,19,14,23,23,23,25,18,18,18,4,3}

    {21,24,1,1,7,20,20,20,15,17,17,17,22,12,12,12,8,13,13,13,9,6,6,6,11,5,5,5,10,16,16,16,19,14,14,14,23,25,25,25,18,4,4,4,3,2,2,2}

    Returns: 200

  16. 25

    {18,18,18,24,19,19,19,13,25,25,21,23,23,23,4,11,11,11,6,6,6,2,16,16,16,1,17,17,17,10,7,7,3,12,12,12,9,14,14,14,5,20,20,20,22,15,15,15,8}

    {18,24,19,19,19,13,25,25,25,21,21,21,23,4,4,4,11,6,6,2,16,16,16,1,17,17,17,10,7,7,7,3,3,3,12,9,9,9,14,5,5,5,20,22,22,22,15,8,8}

    Returns: 4

  17. 25

    {10,24,22,22,9,9,9,14,14,14,6,19,19,19,15,2,2,2,5,5,5,4,4,4,7,13,13,20,20,20,16,16,16,23,23,1,25,25,8,17,17,12,12,3,21,21,11,11}

    {10,10,10,24,24,22,9,9,14,6,6,6,19,15,15,15,2,5,5,4,7,7,13,20,20,20,16,16,23,1,1,25,8,8,17,17,17,12,12,12,3,3,21,21,21,11,11,18}

    Returns: 100

  18. 25

    {20,20,20,7,7,7,25,21,21,21,6,3,3,3,10,12,12,12,24,5,5,5,16,9,9,9,14,15,15,15,11,13,13,13,22,19,19,19,8,18,18,18,1,2,2,2,4,23}

    {20,7,25,25,21,6,6,6,3,10,10,10,12,24,24,24,5,16,16,16,9,14,14,14,15,11,11,11,13,22,22,22,19,8,8,8,18,1,1,1,2,4,4,4,23,17,17,17}

    Returns: 200

  19. 50

    {42,42,42,33,29,29,29,47,41,41,41,35,40,40,40,24,37,37,8,7,7,7,26,45,45,45,49,18,18,18,14,22,22,22,15,38,38,38,39,39,36,48,48,48,30,34,34,34,46}

    {42,33,29,29,29,47,41,41,41,35,40,40,40,24,37,37,37,8,8,8,7,26,26,26,45,49,49,49,18,14,14,14,22,15,15,15,38,39,39,36,36,36,48,30,30,30,34,46,46}

    Returns: 377024777

  20. 20

    {8,4,2,2,11,11,11,10,7,7,7,13,12,12,12,19,1,1,1,3,3,3,17,5,5,5,14,20,20,20,16,9,9,9,18,6,6,15}

    {8,8,8,4,4,2,11,11,11,10,7,7,7,13,12,12,12,19,1,3,17,5,5,5,14,20,20,20,16,9,9,9,18,6,6,6,15,15}

    Returns: 64

  21. 31

    {31,31,31,23,4,4,4,16,19,19,21,10,10,10,1,30,30,30,6,6,6,18,18,12,12,12,20,14,27,27,27,3,9,9,9,15,7,7,7,24,26,26,26,22,29,29,29,8,17,17}

    {31,23,4,4,4,16,19,19,19,21,21,21,10,1,1,1,30,6,6,18,25,25,11,12,20,14,14,14,27,3,9,9,9,15,7,7,7,24,26,26,26,22,29,29,29,8,17,17,17,13}

    Returns: 332404386

  22. 37

    {20,20,20,4,28,28,28,7,29,29,29,34,16,16,16,32,24,24,24,8,18,18,18,15,10,10,10,21,12,12,12,31,14,5,5,5,17,35,35,35,37,1,1,1,23,26,26,26,11,36}

    {20,4,28,28,28,7,29,29,29,34,16,16,16,32,24,24,24,8,18,18,18,15,10,10,10,21,12,12,12,31,14,14,14,5,17,35,35,35,37,1,1,1,23,26,26,26,11,36,36,36}

    Returns: 96160863

  23. 48

    {42,42,42,34,44,44,44,17,27,25,25,25,47,29,29,46,5,5,15,15,15,16,10,10,10,19,19,9,9,9,40,13,13,13,33,26,35,35,22,23,23,23,11,12,12,12,38,37,37,37}

    {42,34,44,44,44,17,27,27,27,25,47,29,29,29,46,46,46,5,5,15,16,16,16,10,19,19,43,9,40,13,13,13,33,26,26,26,35,22,22,22,23,11,11,11,12,38,38,38,37,24}

    Returns: 173188458

  24. 28

    {9,24,25,25,25,11,4,4,4,13,20,20,20,26,19,19,19,1,6,23,23,23,18,10,10,10,3,7,7,7,28,8,21,21,21,27,14,14,14,15,2,17,17,22,22,16,16,5,5,12}

    {9,9,9,24,25,25,25,11,4,4,4,13,20,20,20,26,19,1,1,1,6,23,23,23,18,10,10,10,3,7,28,28,28,8,21,21,21,27,14,14,2,2,17,17,22,22,16,16,5,5}

    Returns: 9289728

  25. 42

    {26,26,1,1,38,38,16,16,24,24,18,18,10,10,36,36,37,29,29,29,41,42,42,42,5,12,12,12,25,40,40,40,23,34,34,34,39,35,35,35,20,33,33,7,7,27,27,11,11,30}

    {26,1,1,38,38,16,16,24,24,18,18,10,10,36,36,37,37,29,41,42,42,42,5,12,12,12,25,40,40,40,23,34,34,34,39,35,35,35,20,33,33,33,8,7,27,27,11,11,30,30}

    Returns: 787120819

  26. 26

    {4,4,25,11,11,11,15,23,23,23,16,24,24,26,26,26,13,6,6,6,9,7,7,7,22,5,5,5,8,21,18,18,14,14,20,20,3,3,12,12,1,1,2,2,10,10,17,17,19,19}

    {4,25,25,25,11,15,15,15,23,16,16,16,24,24,26,13,13,13,6,9,9,9,7,22,22,22,5,8,8,21,21,18,18,14,14,20,20,3,3,12,12,1,1,2,2,10,10,17,17,19}

    Returns: 8

  27. 27

    {3,3,3,4,20,20,20,12,6,6,6,25,16,16,16,5,11,11,11,2,15,15,15,1,21,22,22,22,27,18,18,18,19,10,10,10,17,23,23,23,13,9,9,24,24,24,26,7,7,7}

    {3,4,20,20,20,12,6,6,6,25,16,16,16,5,11,11,11,2,15,15,15,1,21,21,21,22,27,18,18,18,19,10,10,10,17,23,23,23,13,9,9,9,24,24,26,7,7,7,14,8}

    Returns: 89856

  28. 27

    {23,11,15,15,15,14,14,14,16,13,13,13,12,25,25,25,18,10,10,10,19,27,27,27,22,6,6,6,4,2,2,2,5,1,1,1,7,26,26,26,24,9,9,9,3,21,21,21,20,8}

    {23,23,23,11,15,15,14,16,16,16,13,12,12,12,25,18,18,18,10,19,19,19,27,22,22,22,6,4,4,2,5,1,1,1,7,26,26,26,24,9,9,9,3,21,21,21,20,8,8,8}

    Returns: 46656

  29. 50

    {29,29,29,24,10,10,10,42,31,31,31,35,34,34,34,13,44,26,26,26,45,27,27}

    {29,24,10,10,10,42,31,31,31,35,34,34,34,13,44,44,44,26,45,27,27,27,23}

    Returns: 432230828

  30. 42

    {37,41,33,33,33,2,39,39,39,15,30,30,30,25,10,10,9,1,13,27,27,27,18,3,3,3,14,21,21,21,12,19,19,19,5,26,35,35,35,31,32,32,32,22,7,7,7,11,20,17}

    {37,37,37,41,33,33,33,2,39,39,30,25,10,10,10,9,9,1,1,1,13,27,27,27,18,3,3,3,14,21,21,21,12,19,5,5,5,26,35,35,35,31,32,32,32,22,7,7,20,20}

    Returns: 462456458

  31. 34

    {25,4,34,34,34,17,16,16,16,33,12,29,29,31,8,8,8,22,14,14,14,18,6,6,28,28,3,3,13,13,10,24,11,11,11,32,21,21,21,7,23,23,23,15,2,2,2,30,27,27}

    {25,25,25,4,34,34,34,17,16,33,33,33,12,12,12,29,31,31,31,8,22,18,18,6,6,28,28,3,3,13,10,10,10,24,11,11,11,32,21,21,21,7,23,23,23,15,2,2,2,30}

    Returns: 971863648

  32. 31

    {28,28,28,19,4,4,4,25,3,3,7,7,7,9,30,30,30,15,23,23,23,27,24,24,24,10,11,11,16,16,16,29,13,13,13,20,14,14,14,17,6,6,6,2,26,26,26,22,5,5}

    {28,19,4,4,4,25,3,3,3,12,7,9,30,30,30,15,23,23,23,27,24,24,24,10,11,11,11,18,16,29,13,13,13,20,14,14,14,17,6,6,6,2,26,26,26,22,5,5,5,31}

    Returns: 166202193

  33. 34

    {2,2,2,31,30,30,3,3,3,21,34,34,34,29,29,18,18,20,20,26,26,23,23,19,19,22,22,16,16,24,24,9,9,11,11,14,14,8,8,5,5,12,32,32,32,28,33,33,33,13}

    {2,31,30,30,30,17,3,21,34,34,34,29,7,7,27,18,20,20,26,26,23,23,19,19,22,22,16,16,24,24,9,9,11,11,14,14,8,8,5,5,12,12,32,28,33,33,33,13,10,10}

    Returns: 45417713

  34. 29

    {7,23,5,5,5,11,11,11,26,29,29,3,28,28,28,10,10,10,22,24,24,24,17,9,9,9,19,14,14,14,8,4,4,25,16,16,16,21,21,21,2,12,12,12,27,13,13,13,18,18}

    {7,7,7,23,5,5,11,26,26,26,29,29,29,3,28,28,10,22,22,22,24,17,17,17,9,19,19,19,14,8,8,8,4,25,25,16,21,21,2,12,12,12,27,13,13,13,18,15,15,20}

    Returns: 405751759

  35. 35

    {11,11,11,34,14,14,14,8,5,5,29,29,25,25,18,18,16,16,22,22,28,28,27,27,19,19,23,1,1,1,10,15,15,15,17,30,30,30,31,21,21,21,20,32,32,32,13,4,4,4}

    {11,34,14,14,14,8,5,5,5,3,29,12,25,18,18,16,16,22,22,28,28,27,27,19,19,23,23,1,10,15,15,15,17,30,30,30,31,21,21,21,20,32,32,32,13,4,4,4,24,35}

    Returns: 636698040

  36. 28

    {2,2,2,3,9,9,9,4,11,11,11,5,16,16,16,7,17,17,27,27,15,15,23,23,20,20,21,21,13,13,18,18,28,28,25,25,12,12,6,26,26,26,8,19,19,19,22,10,10,10}

    {2,3,9,9,9,4,11,11,11,5,16,16,16,7,17,17,17,14,27,15,15,23,23,20,20,21,21,13,13,18,18,28,28,25,25,12,12,6,6,26,8,19,19,19,22,10,10,10,24,1}

    Returns: 7547904

  37. 33

    {32,1,1,4,4,16,16,21,20,24,24,25,9,9,9,30,30,30,6,7,7,11,18,18,19,8,8,8,3,31,31,31,22,22,22,15,12,12,12,2,29,5,10,10,10,23,27,27,27,13}

    {32,32,1,1,4,4,16,21,21,21,20,20,20,24,25,25,9,30,30,30,6,6,6,7,7,7,11,18,18,18,19,8,8,3,31,31,31,22,15,15,29,29,29,5,10,10,10,23,27,27}

    Returns: 23697941

  38. 41

    {27,19,7,7,7,8,6,6,6,11,14,35,16,16,16,32,33,33,33,30,1,1,1,26,4,4,4,15,10,10,10,40,5,5,5,38,2,2,2,13,41,41,41,17,25,25,25,18,28,34}

    {27,27,27,19,7,7,7,8,6,6,14,14,14,35,16,16,16,32,33,33,33,30,1,1,1,26,4,4,4,15,10,10,10,40,5,5,5,38,2,2,2,13,41,41,41,17,25,25,28,28}

    Returns: 594204132

  39. 32

    {2,27,27,15,15,5,5,18,18,8,8,3,3,25,25,4,4,13,13,17,17,29,29,7,7,21,21,31,31,19,19,6,28,14,9,9,24,24,20,20,22,22,11,11,1,1,23,23,32,10}

    {2,2,27,27,15,15,5,5,18,18,8,8,3,3,25,25,4,4,13,13,17,17,29,29,7,7,21,21,31,31,19,6,6,14,14,9,9,24,24,20,20,22,22,11,11,1,1,23,32,32}

    Returns: 315040173

  40. 28

    {7,7,7,13,15,15,15,9,25,25,25,5,6,6,6,2,28,21,21,21,24,19,19,19,16,1,1,1,18,11,11,11,10,10,10,3,22,22,22,14,23,23,23,26,26,8,8,8,4,20}

    {7,13,15,15,15,9,25,25,25,5,6,6,6,2,28,28,28,21,24,19,19,19,16,1,1,1,18,11,11,11,10,3,3,22,14,14,14,23,26,26,26,27,17,17,12,8,4,20,20,20}

    Returns: 30191616

  41. 5

    {1,5,5,2,2,4,4,3,3,3}

    {1,1,5,5,2,2,4,4,3,1}

    Returns: 0

  42. 25

    {14,1,1,24,24,19,19,25,25,13,13,23,23,16,16,8,8,22,22,2,2,10,10,11,11,17,17,15,15,3,3,6,6,12,12,7,7,18,18,20,20,21,21,9,9,5,5,4,4,4}

    {14,14,1,1,24,24,19,19,25,25,13,13,23,23,16,16,8,8,22,22,2,2,10,10,11,11,17,17,15,15,3,3,6,6,12,12,7,7,18,18,20,20,21,21,9,9,5,5,4,14}

    Returns: 0

  43. 20

    {14,17,17,9,9,16,16,2,2,8,8,3,3,20,20,7,7,6,6,1,1,19,19,12,12,4,4,10,10,10}

    {14,14,17,17,9,9,16,16,2,2,8,8,3,3,20,20,7,7,6,6,1,1,19,19,12,12,4,4,10,14}

    Returns: 0

  44. 50

    {48,48,32,32,19,19,41,41,23,23,25,48}

    {48,32,32,19,19,41,41,23,23,25,25,25}

    Returns: 0

  45. 50

    {7,7,22,22,23,23,32,32,26,26,40,7,9,39,34,35,25,37,9,28,4,12}

    {7,22,22,23,23,32,32,26,26,40,40,40,20,38,12,8,48,48,37,27,19,29}

    Returns: 0

  46. 5

    {2,2,2,1,1,5,5,5,3,3}

    {2,1,4,1,4,1,5,3,1,5}

    Returns: 0

  47. 5

    {2,2,2,2,2,5,5,5,4,4,4,4,1,1,1,1,1,3,3,3}

    {2,5,4,1,3,5,4,1,5,4,1,3,2,5,4,1,3,2,1,3}

    Returns: 0

  48. 7

    {7,7,7,7,7,7,2,2,2,2,5,5,5,5,5,1,1,1,1,1,1,3,3,3,3,3,3,3,4,4,4,4,4,6,6,6,6,6,6,6}

    {7,2,5,1,3,6,2,5,1,3,5,1,3,4,6,2,5,1,3,4,6,7,2,5,1,3,4,6,7,2,5,4,6,7,2,5,1,3,4,6}

    Returns: 0

  49. 7

    {4,1,7,5,6,7,2,5,1,3,6,4,1,3,7,2,5,4,1,3,6,2,5,1,6,7,5,1,7,2}

    {5,5,5,4,4,4,4,1,1,1,1,3,3,3,3,3,6,6,6,6,6,6,7,7,7,7,2,2,2,2}

    Returns: 0

  50. 7

    {1,1,1,2,2,7,7,6,6,6,6,4,4,4,5,5,5,5,3,3}

    {1,7,3,1,3,2,5,7,6,4,5,2,6,4,1,2,6,5,2,4}

    Returns: 0

  51. 23

    {18,5,18,5,18,2,5,23,23,23,13,16,16,12,8,8,8,4,11,11,9,10,10,10,6,6,6,7,22,22,22,14,20,20,20,17,15,15,15,21,19,19,19,3,3}

    {18,18,2,2,5,5,5,23,13,16,16,16,12,12,12,8,4,4,4,11,11,11,9,10,10,6,7,7,7,22,14,14,14,20,17,17,17,15,21,21,21,19,3,3,1}

    Returns: 0

  52. 46

    {4,23,21,21,17,28,28,28,29,3,3,3,11,30,30,30,34,1,1,1,10,10,42,44,33,33,20,27,27,22,18,18,32,40,25,25,25,37,9,9,8,13,13,13,14,45,45,15,15,15}

    {4,4,4,23,23,23,21,17,17,17,28,29,29,29,3,11,11,11,30,34,34,1,1,44,44,33,20,20,27,22,22,18,32,32,32,40,25,25,25,37,37,37,9,8,8,8,13,13,14,45}

    Returns: 69307265

  53. 47

    {47,38,1,1,29,31,31,19,44,44,44,4,28,28,28,42,17,17,17,41,7,7,10,6,6,27,21,21,14,14,14,11,43,43,43,20,46,46,46,23,5,5,5,34,35,35,35,13,37,37}

    {47,47,47,38,38,38,1,1,1,29,31,31,31,19,44,44,44,4,28,41,41,7,10,10,6,27,27,21,14,11,43,43,43,20,46,46,46,23,5,5,5,34,35,35,35,13,37,37,37,3}

    Returns: 366395265

  54. 49

    {39,19,19,38,5,5,5,6,6,12,26,26,42,17,17,18,18,8,8,15,7,7,35,11,11,48,3,20,20,20,16,31,4,4,14,27}

    {39,39,19,38,38,5,6,6,12,12,12,26,42,42,17,17,18,18,8,15,15,7,35,35,11,48,48,48,3,20,20,31,31,4,14,14}

    Returns: 413368476

  55. 49

    {14,14,14,3,39,49,49,44,45,45,17,15,15,15,29,7,7,7,35,6,6,6,33,21,21,21,32,47,47,47,36,28,28,28,16,22,22,22,20,24,26,26,18,31,31,2,4,4,38}

    {14,3,39,39,39,49,44,44,45,17,17,15,29,7,7,7,35,6,6,6,33,21,21,21,32,47,47,47,36,28,28,28,16,22,22,22,20,24,24,24,26,18,18,31,2,2,4,38,38}

    Returns: 14158193

  56. 48

    {32,32,32,17,8,8,8,34,31,31,31,24,37,23,23,29,44,44,5,16,16,16,13,10,10,10,22,22,22,36,3,3,3,26,9,9,35,30,30,30,6,12,12,12,45,4,4,4,33,46}

    {32,17,8,8,8,34,31,31,31,24,37,37,37,23,29,29,44,5,5,16,13,10,10,10,22,36,36,3,26,26,26,9,35,35,35,30,30,30,6,12,12,12,45,4,4,4,33,46,46,46}

    Returns: 378234047

  57. 35

    {18,18,18,11,21,21,21,16,24,24,24,10,5,5,5,25,3,3,3,8,13,13,13,35,14,14,14,2,17,4,4,23,23,33,33,6,6,26,26,29,29,30,30,12,12,31,31,19,19,9}

    {18,11,21,21,21,16,24,24,24,10,5,5,5,25,3,3,3,8,13,13,13,35,14,14,14,2,17,17,17,4,23,23,33,33,6,6,26,26,29,29,30,30,12,12,31,31,19,19,9,9}

    Returns: 861765924

  58. 28

    {22,22,15,21,21,21,6,7,7,7,26,14,14,23,23,10,19,19,4,4,17,17,3,3,8,8,16,16,24,24,11,11,5,5,2,2,20,20,9,9,13,13,28,28,1,1,12,27,27,25}

    {22,15,15,21,6,7,7,7,26,14,14,14,18,23,10,10,19,4,4,17,17,3,3,8,8,16,16,24,24,11,11,5,5,2,2,20,20,9,9,13,13,28,28,1,1,12,12,27,25,25}

    Returns: 215040

  59. 28

    {5,28,25,25,25,27,11,11,24,3,22,22,22,19,6,6,6,13,26,26,26,10,20,20,20,17,18,18,18,9,4,4,4,1,16,16,16,14,15,15,15,2,21,21,21,23,7,7,8,12}

    {5,5,5,28,25,27,27,11,24,24,24,3,22,22,22,19,6,6,6,13,26,26,26,10,20,20,20,17,18,18,18,9,4,4,4,1,16,16,16,14,15,15,15,2,21,23,23,7,8,8}

    Returns: 1720320

  60. 36

    {9,8,30,30,30,5,21,21,21,34,18,18,18,29,32,32,32,4,26,26,26,7,2,2,10,23,6,6,6,15,12,12,12,11,20,20,19,33,33,22,22,22,25,3,3,24,24,24,17,28}

    {9,9,9,8,30,30,30,5,21,21,21,34,18,18,18,29,32,32,32,4,26,7,7,2,10,10,10,23,6,6,6,15,12,11,11,20,19,19,33,33,22,25,25,25,3,3,24,17,17,17}

    Returns: 821023815

  61. 37

    {30,20,20,4,4,1,1,25,25,29,23,34,34,2,2,5,5,8,8,3,3,16,16,9,9,22,22,13,13,19,19,24,24,37,32,17,36,36,36,33,18,18,18,15,28,28,28,7,11,35}

    {30,30,20,20,4,4,1,1,25,29,23,23,34,34,2,2,5,5,8,8,3,3,16,16,9,9,22,22,13,13,19,19,24,37,32,32,32,17,36,36,36,33,18,18,18,15,28,7,7,7}

    Returns: 598423943

  62. 34

    {23,2,2,2,21,21,21,17,13,13,13,1,9,9,9,33,24,24,24,34,4,4,4,32,10,10,10,22,14,14,14,29,18,18,18,5,31,31,3,26,26,26,16,30,30,30,12,19,19,19}

    {23,2,21,17,17,13,1,1,1,9,33,33,33,24,34,34,34,4,32,32,32,10,22,22,22,14,29,29,29,18,5,5,5,31,11,11,11,15,3,26,16,30,30,30,12,19,19,19,27,20}

    Returns: 261354430

  63. 36

    {29,11,11,2,2,17,17,21,21,30,30,15,15,23,23,18,18,4,32,35,16,8,22,22,22,33,10,10,26,26,26,27,9,9,9,5,28,28,28,6,24,24,24,19,14,14,14,13,13,34}

    {29,11,2,2,17,17,21,21,30,30,15,15,23,23,18,18,4,4,32,35,16,8,8,22,33,33,33,10,10,26,27,27,27,9,5,5,5,28,6,6,6,24,19,19,19,14,13,13,34,34}

    Returns: 339135904

  64. 47

    {18,18,13,13,21,21,4,4,8,8,34,37,7,7,7,30,9,9,9,43,43,43,35,42,42,42,29,29,31,17,17,17,23,16,16,16,6,24,24,24,32,1,1,19,19,20,20,40,40,45}

    {18,13,13,21,21,4,4,8,8,34,34,37,7,30,9,9,9,43,35,35,42,29,29,29,31,17,17,23,23,23,16,6,6,6,12,5,5,24,32,1,1,1,22,19,20,20,40,40,45,45}

    Returns: 524936832

  65. 36

    {29,29,29,11,11,11,26,13,13,24,14,14,14,32,16,16,16,4,2,2,2,8,6,6,6,25,25,25,18,30,30,30,36,34,20,20,20,17,15,15,15,7,21,21,21,1,12,12,12,33}

    {29,11,26,26,13,24,24,24,14,14,14,32,16,16,16,4,2,2,2,8,6,6,6,25,18,18,30,36,36,36,34,23,23,23,20,17,15,15,15,7,21,21,21,1,12,12,12,33,10,10}

    Returns: 967731254

  66. 28

    {2,22,24,18,8,8,8,25,12,12,12,3,17,17,17,5,10,21,21,9,9,4,4,7,7,16,16,19,19,13,13,27,27,26,26,20,20,1,1,6,6,15,15,28,28,23,23,14,14,11}

    {2,22,24,24,24,18,8,8,8,25,12,12,12,3,17,17,10,10,21,21,9,9,4,4,7,7,16,16,19,19,13,13,27,27,26,26,20,20,1,1,6,6,15,15,28,28,23,23,14,14}

    Returns: 145152

  67. 49

    {33,17,17,7,41,25,31,31,31,43,38,38,38,29,2,2,2,45,45,45,40,21,30,22,22,22,18,39,39,5,11}

    {33,33,17,7,41,41,41,25,31,31,31,43,38,38,38,29,2,2,45,40,40,21,21,21,30,22,18,18,39,5,5}

    Returns: 88201078

  68. 44

    {6,6,28,29,29,29,25,25,25,41,41,41,14,23,23,35,33,33,33,37,7,43,43,43,26,21,21,21,44,10,10,10,38,22,22,34,34,34,4,42,42,42,24,24,24,20,40,40,40,30}

    {6,28,28,28,29,25,25,41,14,14,23,35,35,35,33,33,33,37,7,7,7,43,26,21,21,21,44,10,10,10,38,22,22,22,34,34,4,42,42,42,24,20,20,40,30,30,30,17,3,3}

    Returns: 677412309

  69. 35

    {34,34,6,6,26,26,7,7,33,35,8,8,24,24,24,16,3,3,23,21,21,21,1,17,17,17,12,31,31,31,22,10,10,10,25,4,4,4,15,20,20,20,29,19,19,19,27,5,5,5}

    {34,6,6,26,26,7,7,33,33,35,8,24,24,16,3,3,3,23,23,23,21,1,1,1,17,12,12,31,22,10,10,10,25,4,4,4,15,20,20,20,29,19,19,19,27,5,5,5,9,28}

    Returns: 408310032

  70. 39

    {33,4,39,39,39,17,22,22,22,34,25,25,25,14,3,3,3,15,35,35,35,7,6,6,6,27,19,19,19,26,1,1,1,32,16,16,28,11,21,18,18,18,36,5,5,5,2,12,12,12}

    {33,33,33,4,39,39,39,17,22,22,22,34,25,25,25,14,3,3,3,15,35,35,35,7,6,6,6,27,19,19,19,26,1,1,1,32,32,11,11,11,21,18,18,18,36,5,5,5,2,12}

    Returns: 86194805

  71. 27

    {17,12,6,10,10,10,21,16,16,16,25,25,2,2,26,26,26,8,23,23,23,22,11,11,11,18,9,9,9,5,24,24,24,1,19,19,19,15,15,14,20,20,20,4,13,13,13,3,27,27}

    {17,12,12,12,6,10,10,10,21,16,16,25,25,2,26,8,23,23,23,22,11,11,11,18,9,9,9,5,24,24,24,1,19,19,19,15,14,14,20,20,20,4,13,13,13,3,27,27,27,7}

    Returns: 2592

  72. 46

    {38,35,35,20,5,5,5,24,14,14,14,17,39,39,39,1,44,44,44,25,29,29,29,12,12,12,18,3,3,3,34,34,34,10,10,10,45,26,13,13,4,4,41,41,33,33,28,28,21,21}

    {38,38,35,35,35,20,5,5,5,24,14,14,14,17,39,39,39,1,44,44,44,25,29,29,12,18,18,18,3,34,34,10,45,45,26,27,27,27,13,4,4,41,41,33,33,28,28,21,21,7}

    Returns: 991257803

  73. 49

    {30,43,43,43,38,29,29,29,25,49,49,49,10,8,8,8,17,48,48,48,15,34,34,34,40,41,41,41,2,19,28,20,35,42,42,42,14,7,7,7,39,32,32,32,22,11,11,11,36,36}

    {30,43,38,29,29,29,25,49,49,49,10,8,8,8,17,48,48,48,15,34,34,34,40,41,41,41,2,19,19,19,28,20,35,42,14,7,7,7,39,32,32,32,22,11,11,11,36,21,21,23}

    Returns: 571151207

  74. 44

    {22,19,19,19,31,43,43,43,40,28,28,28,16,25,25,25,20,15,15,15,7,5,5,5,33,29,29,29,27,32,32,32,23,8,8,8,2,12,12,13,36,18,18,14,41,41,41,44,9,9}

    {22,19,31,43,43,43,40,28,28,28,16,25,25,25,20,15,15,15,7,5,5,5,33,29,29,29,27,32,32,32,23,8,8,8,2,12,12,12,35,13,36,18,14,14,14,41,44,44,44,9}

    Returns: 725392881

  75. 50

    {24,24,45,45,34,34,25,9,18,18,13,13,13,32,16,16,16,44,3,3,3,29,21,21,21,11,48,48,49,36,31,31,4,4,10,37,37,37,40,6,6,6,26,23,23,23,1,43,43,43}

    {24,45,45,34,34,25,25,9,18,30,13,32,16,16,16,44,3,3,3,29,21,21,21,11,48,48,48,33,49,36,31,4,4,10,10,37,40,6,6,6,26,23,23,23,1,43,43,43,39,5}

    Returns: 569190716

  76. 48

    {23,6,34,34,34,13,40,40,40,45,1,1,1,37,3,3,3,8,17,17,17,30,20,20,20,31,33,24,25,25,2,11,11,11,36,10,10,14,7,7,7,19,41,41,41,21,43,16,18,48}

    {23,23,23,6,34,34,34,13,40,40,40,45,1,1,1,37,3,3,3,8,17,17,17,30,20,20,33,33,33,24,24,24,25,2,2,2,11,11,11,36,10,10,10,14,7,7,43,43,18,18}

    Returns: 969294008

  77. 46

    {45,18,25,25,25,42,42,42,2,34,34,43,43,43,8,22,22,22,11,9,9,9,44,31,31,31,41,13,13,13,37,10,10,10,1,46,46,20,27,40,40,40,3,14,14,14,6,29,29,29}

    {45,45,45,18,25,25,42,2,2,2,34,43,8,22,22,22,11,9,9,9,44,31,31,31,41,13,13,13,37,10,10,10,1,46,46,46,5,20,20,20,27,40,40,40,3,14,14,14,6,29}

    Returns: 906937476

  78. 32

    {32,16,8,8,24,24,7,7,17,17,21,21,11,11,25,25,10,10,27,27,22,22,9,9,1,1,29,29,18,14,5,20,30,26,31,6,6,6,28,3,3,3,12,19,19,19,4,2,2,2}

    {32,16,16,8,8,24,24,7,7,17,17,21,21,11,11,25,25,10,10,27,27,22,22,9,9,1,1,29,18,14,5,20,30,26,26,26,31,6,6,6,28,3,3,3,12,19,19,19,4,2}

    Returns: 426912515

  79. 49

    {6,7,3,31,31,22,22,29,29,49,49,40,40,11,11,47,47,44,44,20,16,27,27,30,30,32,32,43,43,34,34,19,19,42,42,48,48,41,41,37,37,46,46,15,15,36,36,39,39,23}

    {6,7,3,3,31,31,22,22,29,29,49,49,40,40,11,11,47,47,44,20,16,16,27,27,30,30,32,32,43,43,34,34,19,19,42,42,48,48,41,41,37,37,46,46,15,15,36,36,39,23}

    Returns: 373050828

  80. 28

    {4,2,24,9,9,8,8,26,26,10,10,5,5,6,6,20,20,14,14,16,16,27,27,3,3,18,18,28,28,25,25,19,19,17,17,21,21,12,11,11,23,23,1,1,13,13,7,7,22,22}

    {4,2,24,9,8,8,26,26,10,10,5,5,6,6,20,20,14,14,16,16,27,27,3,3,18,18,28,28,25,25,19,19,17,17,21,21,12,12,11,23,23,1,1,13,13,7,7,22,22,15}

    Returns: 13440

  81. 10

    {7,4,4,3,3,5,5,1,1,6,6,9,9,10,10,10,8,2}

    {7,7,4,4,3,3,5,5,1,1,6,6,9,9,10,8,8,8}

    Returns: 40

  82. 4

    {3,3,1,2,2,1}

    {3,1,1,1,2,4}

    Returns: 0

  83. 10

    {6,6,9,9,7,7,5,5,10,10,8,8,3,3,4,1,1,4}

    {6,9,9,7,7,5,5,10,10,8,8,3,3,4,4,4,1,2}

    Returns: 0

  84. 20

    {3,17,17,11,11,7,7,15,15,12,12,16,16,1,1,19,19,5,5,10,10,18,18,8,8,13,13,2,2,20,20,6,6,9,9,9,14,4}

    {3,3,17,17,11,11,7,7,15,15,12,12,16,16,1,1,19,19,5,5,10,10,18,18,8,8,13,13,2,2,20,20,6,6,9,14,14,9}

    Returns: 0

  85. 10

    {8,2,7,7,7,1,4,4,4,10,9,9,9,6,6,6,5,3}

    {8,8,8,2,7,7,7,1,4,4,4,10,9,9,6,5,5,6}

    Returns: 0

  86. 20

    {15,15,15,14,7,7,7,10,2,2,2,5,6,6,6,19,16,16,16,18,4,4,4,17,13,13,13,12,3,3,3,9,11,11,8,20,20,8}

    {15,14,7,7,7,10,2,2,2,5,6,6,6,19,16,16,16,18,4,4,4,17,13,13,13,12,3,3,3,9,11,11,11,8,8,8,20,1}

    Returns: 0

  87. 20

    {4,14,1,1,1,10,2,2,2,7,9,9,9,20,18,18,18,15,12,12,12,8,11,11,11,19,13,13,13,6,5,5,5,16,16,16,3,17}

    {4,4,4,14,1,1,1,10,2,2,2,7,9,9,9,20,18,18,18,15,12,12,12,8,11,11,11,19,13,13,13,6,5,5,16,3,3,16}

    Returns: 0

  88. 20

    {16,19,19,19,9,9,4,4,13,12,12,5,5,15,15,18,10,10,6,6,2,8,8,8,7,7,7,11,11,11,3,20,20,20,14,17,17,14}

    {16,16,19,9,9,4,4,13,13,13,12,12,5,5,15,15,15,18,18,10,10,10,6,2,2,8,7,7,11,3,3,3,20,14,14,14,17,1}

    Returns: 0

  89. 20

    {11,11,11,2,14,14,10,5,5,18,9,9,9,15,15,15,4,20,20,20,6,16,16,16,19,8,8,8,17,3,3,3,1,1,13,12,12,13}

    {11,2,14,14,14,10,10,10,5,5,5,18,9,9,15,4,4,4,20,6,6,6,16,19,19,19,8,17,17,17,3,1,1,13,13,13,12,7}

    Returns: 0

  90. 40

    {35,35,35,26,10,10,10,38,1,1,40,40,17,13,13,13,9,24,34,37,37,2,2,11,11,31,31,6,6,32,32,25,25,12,12,28,28,3,36,4,4,4,19,23,30,14,14,14,18,29}

    {35,26,10,10,10,38,1,1,1,40,40,17,17,17,13,9,9,13,34,34,37,37,2,2,11,11,31,31,6,6,32,32,25,25,12,12,28,3,3,3,36,4,4,23,23,23,30,14,14,29}

    Returns: 0

  91. 42

    {16,16,37,37,37,23,19,19,25,7,7,3,3,3,9,38,38,9,14,34,17,17,17,33,33,33,30,20,20,20,8,29,29,29,28,27,27,27,24,2,2,1,1,31,31,41,41,26,26,40}

    {16,37,37,23,19,19,19,25,25,25,7,7,3,9,9,9,38,12,14,14,14,34,17,17,33,30,30,30,20,8,8,8,29,28,28,28,27,24,24,24,2,1,31,31,41,41,26,26,40,40}

    Returns: 0

  92. 33

    {14,14,25,20,20,20,3,16,16,16,1,32,32,15,15,15,28,30,23,8,7,7,7,11,31,31,31,9,12,12,12,6,22,22,22,24,17,17,17,27,2,13,10,10,10,4,19,19,19,21}

    {14,25,25,25,20,3,3,3,16,1,1,1,32,32,15,28,28,15,23,23,23,8,7,7,7,11,31,31,31,9,12,12,12,6,22,22,22,24,17,17,2,2,2,13,10,10,10,4,19,19}

    Returns: 0

  93. 29

    {3,16,7,7,7,17,17,17,18,18,2,23,23,24,24,24,22,13,29,20,5,19,27,27,27,10,21,21,21,25,26,26,12,9,9,9,28,4,4,4,14,6,6,6,11,1,1,1,8,15}

    {3,3,3,16,7,7,17,18,18,2,2,2,23,23,24,22,22,24,29,29,5,5,5,19,27,27,27,10,21,21,21,25,25,25,26,12,12,12,9,28,28,28,4,14,14,14,6,11,11,11}

    Returns: 0

  94. 41

    {1,11,2,2,7,37,37,37,40,38,38,38,38,13,13,13,8,23,24,24,24,31,12,12,16,16,18,18,18,39,41,41,36,9,9,9,15,33,33,29,21,21,21,22,30,30,30,25,35,35}

    {1,1,1,11,11,11,2,7,7,7,37,40,38,38,13,8,8,13,24,31,12,12,12,16,16,18,18,39,41,41,41,36,36,9,15,33,33,33,29,29,29,21,22,22,22,30,25,25,25,35}

    Returns: 0

  95. 50

    {3, 4, 4, 6, 7, 7, 12, 13, 13, 15, 17, 17, 18, 19, 19, 20, 20, 21, 22, 22, 23, 24, 24, 27, 28, 29, 30, 30, 30, 32, 32, 34, 35, 35, 36, 38, 38, 39, 41, 41, 42, 42, 42, 43, 44, 45, 46, 47, 48, 48 }

    {4, 12, 19, 46, 2, 41, 42, 8, 15, 49, 27, 36, 50, 33, 46, 13, 25, 1, 17, 39, 34, 15, 42, 24, 37, 9, 24, 29, 42, 9, 28, 16, 1, 5, 45, 10, 39, 7, 30, 43, 5, 12, 18, 33, 49, 40, 43, 6, 27, 45 }

    Returns: 512538802

  96. 50

    {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 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, 45, 46, 47, 48, 49, 49 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 31, 32, 33, 33, 33, 33, 36, 37, 38, 39, 39, 39, 39, 42, 45, 47, 48, 48, 48, 49 }

    Returns: 135309747

  97. 7

    {1, 1, 1, 2, 3, 4, 5, 6, 7 }

    {1, 2, 3, 1, 2, 3, 1, 2, 3 }

    Returns: 0

  98. 50

    {42, 18, 35, 1, 20, 25, 29, 9, 13, 15, 6, 46, 32, 28, 12, 42, 46, 43, 28, 37, 42, 5, 3, 4, 43, 33, 22, 17, 19, 46, 48, 27, 22, 39, 20, 13, 18, 50, 36, 45, 4, 12, 23, 34, 24, 15, 42, 12, 4, 19 }

    {48, 45, 13, 8, 38, 10, 24, 42, 30, 29, 17, 36, 41, 43, 39, 7, 41, 43, 15, 49, 47, 6, 41, 30, 21, 1, 7, 2, 44, 49, 30, 24, 35, 5, 7, 41, 17, 27, 32, 9, 45, 40, 27, 24, 38, 39, 19, 38, 31, 42 }

    Returns: 0

  99. 5

    {1, 1, 1, 2, 3, 4 }

    {1, 2, 3, 1, 2, 3 }

    Returns: 0

  100. 4

    {1, 1, 1, 2, 3, 4 }

    {2, 3, 4, 2, 3, 4 }

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: