Statistics

Problem Statement for "PrettyLiar"

Problem Statement

This problem has a non-standard time limit: 4 seconds.

Kaede and Kanade are good friends. Today they are going to play a game!

At the beginning of the game, each of them has a sequence of N positive integers. You are given these sequences in the int[]s kaede and kanade.

There is also a single pile of stones. At the beginning of the game the pile consists of S stones. It is guaranteed that S <= sum(kaede) + sum(kanade).

During the game, the players take alternating turns removing some stones from the pile. Kaede takes the first turn. The game is completely deterministic. Each turn looks as follows:

  1. The player notes the value X of the first element of her sequence.
  2. The player erases the first element of her sequence.
  3. The player takes X stones from the pile (or all stones if there are fewer than X stones left).
  4. If the pile just became empty, the player loses the game.

Both girls call themselves "pretty liars", so you should not be surprised that they are going to cheat: before the game, each girl will choose one of the N! possible permutations and use it to permute her sequence in secret.

You, watching the whole process, come up a question: How many of all (N!)^2 possible scenarios will end with Kaede winning the game?

Please compute and return the answer modulo 1,000,000,007.

Definition

Class:
PrettyLiar
Method:
count
Parameters:
int, int[], int[]
Returns:
int
Method signature:
int count(int S, int[] kaede, int[] kanade)
(be sure your method is public)

Notes

  • The constraint on S ensures that one of the girls has to lose the game.

Constraints

  • N will be between 1 and 100, inclusive.
  • kaede will contain exactly N elements.
  • kanade will contain exactly N elements.
  • Each element in kaede will be between 1 and 100, inclusive.
  • Each element in kanade will be between 1 and 100, inclusive.
  • S will be between 1 and 20,000, inclusive.
  • S will be less than or equal to the sum of elements in kaede and kanade.

Examples

  1. 60

    {10,40}

    {20,30}

    Returns: 2

    There are four possibilities: kaede:{10,40} kanade:{20,30} kaede:{10,40} kanade:{30,20} kaede:{40,10} kanade:{20,30} kaede:{40,10} kanade:{30,20} In the first case the game will play out as follows: Kaede removes 10 stones from the pile. After the turn, Kaede's sequence is {40} and there are 50 stones left in the pile. Kanade removes 20 stones from the pile. After the turn, Kanade's sequence is {30} and there are 30 stones left in the pile. Kaede is supposed to take 40 stones. As there are only 30 stones left, she takes those 30 stones and loses the game. Hence, Kanade wins. Kaede wins in two out of the four possibilities listed above: the third and the fourth one. Thus, the correct return value is 2.

  2. 100

    {10,40}

    {20,30}

    Returns: 4

    Regardless of how the girls permute their sequences, Kanade will always lose the game in her second turn. (Note that in this example S is exactly equal to the sum of all girls' numbers.)

  3. 10

    {10,40}

    {20,30}

    Returns: 0

    In every case, Kaede loses in her first turn because S is equal to the smallest element in her sequence.

  4. 25

    {6,14}

    {7,1}

    Returns: 2

  5. 178

    {25,6,14,100,71,49}

    {17,7,1,100,62,43}

    Returns: 240192

  6. 1546

    {50,77,74,23,43,4,57,13,50,94,43,72,94,36,20,23,27,7,3,21,16,64,28,20,2,40,92,93,17,94,43,17,1,87,58,67,43,22,99,76,13,10,45,28,2,5,37,26,76,12}

    {40,93,80,23,20,71,23,14,43,45,38,20,61,84,35,9,85,71,7,21,10,42,23,20,38,73,58,97,32,3,43,99,31,39,33,73,81,3,9,73,17,68,50,27,25,86,22,47,64,8}

    Returns: 949234178

  7. 9727

    {100,100,100,95,98,96,90,97,98,94,90,95,90,100,97,99,99,90,90,96,93,90,98,100,94,96,91,99,94,96,93,99,96,99,95,99,98,98,98,92,96,93,96,99,91,99,96,96,95,99,97,94,93,97,92,97,91,95,96,100,93,95,100,96,92,100,91,93,94,98,96,91,99,96,98,92,92,92,97,92,99,95,90,93,100,92,94,98,96,90,98,96,91,93,92,94,98,100,98,94}

    {93,100,99,93,97,95,92,95,96,97,96,90,99,93,90,100,96,92,90,93,92,100,91,98,93,98,91,95,95,96,99,94,97,93,95,97,96,93,93,100,95,93,98,91,100,90,94,99,100,97,92,92,97,93,99,95,98,93,96,99,97,98,96,94,92,90,93,93,94,91,96,92,98,95,100,97,92,96,97,98,94,97,91,90,93,95,96,99,97,99,93,91,96,93,97,96,97,91,91,93}

    Returns: 768695830

  8. 18937

    {90,97,100,98,95,96,96,91,98,97,90,99,92,97,93,99,100,100,97,94,97,91,96,99,100,98,97,90,97,92,93,94,95,94,96,94,96,93,97,96,100,96,96,92,93,100,93,96,90,93,98,90,91,99,96,99,99,98,93,93,100,92,94,97,97,93,98,91,93,94,92,93,96,97,92,97,98,97,97,92,91,94,92,97,99,96,95,98,99,93,99,97,98,96,98,90,96,92,93,95}

    {100,95,93,93,96,91,94,97,96,91,97,92,99,91,99,93,100,96,95,100,96,99,92,93,99,92,93,100,97,98,91,91,100,92,98,97,91,96,99,100,94,90,94,95,98,98,92,92,95,95,94,92,96,94,96,94,96,95,91,92,99,96,93,97,94,100,92,100,100,96,96,98,99,93,96,92,97,93,100,100,90,95,97,92,98,97,100,98,95,97,94,95,100,94,99,91,90,90,90,97}

    Returns: 0

  9. 17770

    {99,96,97,91,95,94,97,98,91,99,90,100,96,92,100,90,93,98,99,91,97,91,94,97,96,91,100,94,92,100,95,100,98,95,99,100,98,99,94,99,92,93,99,100,98,93,93,98,91,100,93,95,99,91,96,99,91,93,100,97,90,94,93,92,95,96,94,91,100,91,92,97,93,90,100,95,92,97,90,99,96,94,94,94,95,90,95,93,92,92,93,95,90,90,96,97,95,91,97,96}

    {95,100,94,95,94,97,90,95,99,91,97,91,93,99,98,92,100,99,99,91,98,91,94,92,90,95,97,97,93,97,92,92,99,97,96,94,97,91,99,94,91,95,99,99,99,94,99,99,99,93,91,93,97,100,96,92,92,94,92,94,98,93,91,96,96,93,95,90,98,98,98,98,99,97,100,98,93,98,94,98,96,96,99,93,99,97,97,93,90,97,97,96,95,91,93,92,97,97,93,90}

    Returns: 530907952

  10. 8349

    {94,97,97,96,97,99,97,95,97,90,91,90,96,94,93,99,97,100,91,98,94,91,97,93,93,100,98,95,91,100,95,94,94,93,92,95,95,98,96,94,97,90,100,99,97,96,94,93,95,99,97,91,100,90,99,100,92,96,98,94,100,94,94,99,100,96,97,100,99,93,97,91,99,99,94,90,100,94,97,96,93,97,92,92,99,98,100,90,100,97,95,92,90,97,91,99,92,93,97,97}

    {90,96,91,91,93,95,100,97,94,98,91,93,98,97,96,95,100,96,91,92,92,96,92,90,100,92,90,93,98,96,90,98,97,93,95,90,96,91,94,100,91,91,95,94,100,98,93,95,100,95,98,92,91,97,99,95,100,95,92,93,100,98,95,98,94,97,95,91,98,96,98,99,91,92,94,98,94,91,90,100,100,95,90,96,98,90,98,94,95,91,90,93,94,98,97,90,93,96,98,92}

    Returns: 597794272

  11. 18105

    {92,97,97,96,99,93,100,90,99,96,93,96,95,100,95,93,97,91,94,99,91,93,94,96,95,90,95,92,97,100,93,94,93,98,97,94,90,94,100,91,93,98,98,95,91,97,94,91,95,95,94,98,94,91,95,94,96,90,95,100,98,99,99,92,96,98,96,100,93,95,93,98,96,97,95,98,97,90,94,91,97,98,98,97,99,95,91,91,100,96,90,93,95,97,96,100,97,93,90,94}

    {97,90,91,93,98,92,95,97,97,95,96,96,98,98,94,98,93,98,91,90,95,92,95,95,97,95,91,95,98,92,90,95,97,97,90,95,99,95,96,96,90,92,99,97,96,95,90,94,98,100,93,99,90,92,95,99,98,99,97,94,91,95,94,91,91,99,92,96,93,96,96,100,98,92,100,91,94,98,98,90,98,97,95,92,94,98,96,91,92,91,95,98,100,90,99,100,96,92,90,91}

    Returns: 639654178

  12. 18930

    {95,91,93,99,91,99,94,91,91,92,91,97,99,91,98,91,95,93,94,92,100,91,93,96,99,91,99,92,97,93,95,99,95,98,95,95,100,96,98,93,92,93,90,98,98,95,100,98,98,92,99,91,100,97,97,95,92,93,99,90,94,91,97,93,92,90,92,90,95,91,94,94,98,94,95,91,92,93,96,92,100,98,97,95,93,92,96,95,90,92,94,90,94,97,91,92,96,93,91,96}

    {91,91,91,94,97,90,98,99,96,97,90,94,98,91,97,94,96,98,95,94,96,90,99,99,94,94,94,96,93,96,100,93,95,90,99,95,94,90,100,98,97,98,98,92,93,93,94,99,91,96,93,99,92,94,90,94,92,94,100,98,92,90,96,100,98,90,100,99,97,91,98,100,90,100,92,90,90,99,99,94,99,93,93,90,90,96,95,100,90,90,94,98,97,99,98,100,92,99,92,98}

    Returns: 240290891

  13. 18590

    {98,93,99,93,95,95,99,100,100,99,94,93,95,92,92,98,92,97,95,97,99,98,96,92,99,95,90,97,99,94,100,91,99,96,100,92,91,90,94,95,92,96,98,92,97,100,93,100,96,93,90,98,99,96,95,99,96,96,95,93,94,96,91,99,90,95,99,98,94,91,95,98,92,91,93,99,90,96,100,92,93,98,92,94,94,99,100,97,93,97,90,98,94,91,92,95,90,97,95,96}

    {92,99,90,95,97,96,100,90,97,100,97,93,96,100,97,96,100,98,97,92,95,93,90,96,91,95,90,97,93,94,100,99,95,99,91,95,97,91,90,93,99,100,98,95,95,94,99,91,94,95,100,90,90,94,93,96,98,96,95,94,97,98,96,98,93,91,94,94,94,91,96,93,99,99,94,93,98,98,91,97,94,90,93,95,90,92,97,92,95,92,92,99,96,98,95,99,90,98,97,94}

    Returns: 240290891

  14. 18611

    {96,100,99,97,96,97,96,91,100,92,97,97,91,92,95,93,99,98,93,100,92,98,90,98,100,100,90,91,93,90,99,97,94,99,99,98,98,91,94,96,92,100,96,94,97,90,99,96,97,95,97,96,92,91,92,100,90,90,90,99,96,96,92,97,96,97,98,90,96,97,94,92,100,99,92,95,97,96,100,90,95,97,95,96,97,94,90,95,93,90,99,97,96,99,90,96,94,90,95,94}

    {91,97,98,97,95,95,95,90,95,100,97,91,91,97,91,97,90,91,95,97,90,91,92,92,99,99,98,93,96,100,94,92,98,94,90,95,92,95,96,90,98,92,98,99,94,90,96,97,99,91,99,90,100,100,95,93,97,91,100,92,93,94,92,93,96,92,96,99,90,99,91,98,97,94,100,97,95,97,97,90,90,100,93,92,90,90,99,96,94,96,98,97,99,98,99,94,94,90,94,92}

    Returns: 79459745

  15. 18407

    {93,100,99,97,91,90,96,95,98,93,90,95,95,91,90,90,94,90,91,91,91,91,100,98,92,94,99,92,98,100,92,90,98,99,92,91,94,98,98,90,92,100,90,90,95,92,94,100,95,97,97,98,100,93,97,100,98,92,94,97,92,100,90,99,97,100,96,99,97,93,97,93,98,91,93,93,90,97,100,90,99,94,91,94,96,90,91,97,98,98,95,94,99,91,92,94,98,99,99,91}

    {91,92,98,98,98,98,93,92,92,96,93,98,96,99,91,93,96,100,100,96,96,95,91,94,97,94,99,90,94,90,96,92,95,98,94,97,91,93,92,94,98,93,93,91,92,90,98,96,97,97,90,97,95,96,99,91,94,93,97,98,96,91,94,98,90,90,98,97,90,97,91,94,100,92,92,98,94,96,100,92,94,90,93,93,91,96,97,97,95,98,99,96,96,92,91,91,97,99,100,93}

    Returns: 932456712

  16. 3412

    {59,22,16,28,67,4,28,65,51,57,83,37,85,70,100,48,30,95,32,81,27,9,88,9,1,60,19,12,30,36,68,9,43,77,82,32,86,95,48,25,53,91,12,80,99,35,21,71,89,90,24,93,16,15,35,62,78,28,17,76,14,66,28,21,11,67,94,83,13,16,89,86,11,86,91,31,60,51,72,11,25,84,90,42,95,62,41,56,100,42,61,68,12,59,85,22,66,90,3,59}

    {2,42,76,14,38,20,5,29,46,16,36,3,63,84,57,97,59,35,49,88,77,74,79,87,84,72,11,50,26,83,6,94,11,69,9,56,9,69,44,86,51,36,39,67,67,91,80,16,37,61,52,91,37,92,36,86,25,64,87,62,17,28,53,62,58,43,39,16,13,27,40,10,66,28,51,37,6,56,38,89,11,15,28,8,61,16,91,39,91,4,88,42,74,36,73,60,53,72,60,46}

    Returns: 277120416

  17. 4646

    {81,47,47,75,75,65,34,21,44,7,34,93,6,76,3,82,47,64,77,25,34,28,59,100,60,13,57,36,57,70,11,79,75,94,69,18,59,17,11,56,30,12,24,73,51,31,60,33,40,62,21,88,46,46,4,37,6,96,83,30,51,2,35,58,19,94,14,56,99,48,25,53,42,99,11,4,40,72,52,75,24,31,75,47,79,53,37,51,94,70,19,18,11,69,7,87,32,45,40,39}

    {38,90,6,75,59,38,74,14,39,33,41,13,94,99,48,67,53,69,19,75,20,91,54,33,36,18,83,44,27,45,42,61,97,88,55,44,76,100,79,60,57,91,11,86,21,77,92,81,24,9,77,51,9,38,40,5,69,59,94,51,77,8,72,74,78,34,60,48,57,50,47,15,99,60,68,32,58,82,29,8,6,26,57,47,44,14,77,17,7,56,67,39,16,36,68,77,36,88,26,52}

    Returns: 813921037

  18. 8962

    {52,65,42,99,38,31,10,29,28,8,66,91,4,72,62,84,79,90,78,84,70,80,10,75,23,15,34,40,84,96,55,13,92,89,83,13,99,31,71,25,3,97,15,41,82,3,17,65,67,58,32,41,100,23,69,9,69,85,29,40,77,81,67,80,8,25,72,41,86,65,84,66,70,56,39,91,99,95,73,78,59,92,87,35,56,77,53,54,80,3,42,67,65,72,40,97,38,100,31,51}

    {41,3,62,6,74,47,48,52,59,26,78,62,86,62,96,26,29,84,56,65,98,42,60,72,50,1,100,51,70,54,67,90,65,39,50,19,66,44,64,17,41,46,94,79,30,97,98,100,33,66,76,10,68,30,88,97,35,93,82,15,48,7,38,70,60,90,90,85,54,6,44,40,62,21,33,58,86,23,18,3,56,46,3,84,30,3,2,70,91,77,41,13,24,29,5,68,11,39,70,15}

    Returns: 924553356

  19. 4114

    {53,75,74,26,71,51,96,69,100,64,35,80,38,51,57,84,70,6,7,89,41,53,5,85,96,72,95,6,29,38,98,58,78,65,78,21,13,73,37,10,31,81,81,79,31,79,59,14,33,76,30,92,19,37,11,84,65,54,52,80,44,78,40,86,57,57,21,97,64,2,94,81,84,66,55,98,91,41,99,5,72,72,73,11,3,22,93,43,53,65,38,69,15,57,74,99,62,9,56,17}

    {49,35,3,23,43,72,25,86,3,63,76,16,51,55,38,71,87,30,73,13,82,44,92,61,58,65,39,41,98,4,24,24,55,8,17,74,41,18,15,25,66,57,38,15,38,9,44,98,72,30,37,89,71,50,19,18,69,68,11,14,94,19,6,13,60,48,57,91,99,43,26,8,87,75,40,59,82,33,96,17,4,66,100,60,46,78,60,63,21,47,96,97,64,67,9,2,49,33,22,70}

    Returns: 433630948

  20. 746

    {91,95,44,75,96,33,66,88,77,18,96,75,37,10,100,40,24,84,90,7,61,11,65,22,33,76,81,55,95,91,82,82,84,71,57,35,70,55,3,17,37,62,30,47,70,85,21,21,9,33,12,13,31,19,30,18,25,25,58,10,99,20,27,59,20,20,73,36,2,91,59,74,100,31,29,15,3,13,2,73,38,76,41,28,93,18,7,1,57,69,74,64,23,56,1,44,63,23,39,68}

    {97,11,70,63,67,75,19,11,63,30,7,59,71,97,1,86,86,48,48,4,30,82,16,30,78,96,65,86,38,44,38,8,45,49,53,81,16,75,20,15,94,89,21,64,21,90,47,96,32,34,40,33,48,89,90,99,24,81,50,42,43,63,87,6,60,40,10,46,44,13,29,92,75,98,79,2,79,19,95,6,3,17,89,91,27,43,17,93,70,46,46,61,30,37,1,83,88,21,15,37}

    Returns: 53225138

  21. 5770

    {3,66,16,8,56,70,69,14,81,10,82,67,1,2,20,76,90,75,25,95,18,32,58,67,98,5,8,93,96,48,87,39,90,10,57,75,52,71,76,74,86,89,16,28,89,16,89,16,14,24,55,81,79,87,36,67,81,24,68,12,23,36,82,15,13,64,76,5,90,21,17,97,86,87,76,73,90,16,59,18,18,31,5,52,1,78,13,59,56,33,44,24,92,98,5,59,98,9,94,31}

    {68,94,43,75,83,34,25,2,75,97,93,98,4,55,56,62,89,39,33,88,15,14,92,78,18,52,58,60,23,19,55,46,86,97,28,44,47,73,69,98,98,71,37,70,33,14,1,67,92,88,76,88,44,25,69,8,34,87,95,35,84,25,25,18,25,42,85,66,96,20,96,64,43,79,37,81,64,3,47,64,22,89,76,75,16,90,30,46,63,11,75,59,40,91,90,75,77,97,8,35}

    Returns: 476578482

  22. 7106

    {20,30,29,65,28,65,97,10,22,32,96,14,56,22,46,39,100,44,8,75,76,92,28,76,36,70,29,46,88,95,86,65,57,45,23,49,80,29,33,64,36,28,92,40,7,30,9,81,92,76,72,5,33,7,50,25,68,32,84,20,18,25,34,52,94,24,63,63,82,47,22,45,85,92,2,44,79,73,86,72,98,67,83,71,19,73,97,93,9,95,36,63,53,71,46,94,93,62,85,24}

    {3,13,29,27,37,65,39,8,66,40,5,37,29,55,78,69,77,61,52,93,94,88,36,69,98,97,81,16,33,90,24,41,85,37,59,93,96,53,39,72,31,73,11,16,42,44,50,48,38,22,75,35,52,80,45,80,65,26,94,82,74,26,66,60,56,45,12,18,75,22,76,67,23,65,24,90,32,51,60,41,95,60,46,67,64,82,77,74,61,76,3,15,35,89,70,100,17,4,37,60}

    Returns: 440755165

  23. 1608

    {12,68,66,88,93,92,92,68,32,93,94,13,42,63,5,8,45,25,59,78,93,50,75,82,79,24,53,4,65,39,16,43,80,86,38,54,21,98,100,26,80,34,47,94,63,10,52,25,59,87,19,35,76,51,24,16,100,35,67,14,1,50,90,67,28,39,11,91,42,60,8,1,53,11,40,80,53,4,72,32,61,44,81,89,54,28,38,6,33,93,89,23,68,71,90,50,4,65,71,49}

    {28,24,8,70,81,85,98,76,8,86,75,47,85,19,73,57,51,13,43,64,24,92,100,70,95,67,97,10,30,50,61,21,50,100,18,77,6,82,2,56,35,39,63,28,70,56,68,36,58,57,39,2,83,61,72,28,14,50,44,70,24,65,66,93,76,43,97,62,82,88,95,62,91,90,55,18,1,65,3,46,23,6,9,9,17,67,63,100,59,17,17,46,34,89,47,51,45,33,17,23}

    Returns: 240445468

  24. 8350

    {62,50,23,82,7,46,15,88,39,30,13,92,60,35,44,79,9,12,66,97,45,80,74,49,56,19,22,83,16,72,45,17,36,68,30,8,66,78,80,98,94,63,29,52,60,45,93,76,54,38,82,8,68,64,38,75,56,90,60,39,46,71,34,69,47,39,81,14,60,65,33,11,71,71,87,33,26,9,40,10,75,13,32,48,51,27,22,29,62,29,9,74,27,45,15,5,57,4,69,94}

    {16,26,48,41,78,35,43,44,75,85,96,64,11,27,48,99,78,70,43,78,79,92,100,24,97,3,61,68,95,33,78,23,92,88,31,59,89,66,82,21,57,60,23,38,11,83,66,74,71,18,6,57,65,44,44,83,72,18,80,79,16,26,78,74,14,98,98,74,13,97,73,80,87,53,10,52,6,3,94,33,48,96,20,95,31,42,3,19,89,32,19,14,62,45,10,23,27,74,8,96}

    Returns: 535059588

  25. 2864

    {25,40,100,77,7,4,23,93,7,1,38,62,85,59,98,73,21,86,67,17,33,69,30,74,6,66,2,66,37,59,60,22,79,39,65,39,95,45,86,45,75,30,4,36,64,38,1,44,95,99,21,11,57,48,54,57,7,25,16,25,57,12,65,23,33,62,35,38,18,77,44,77,37,6,33,33,81,44,57,76,97,75,10,91,97,51,19,88,28,53,29,31,69,6,91,93,9,20,50,4}

    {58,7,67,59,94,70,14,74,80,9,85,92,85,3,12,29,98,23,7,73,13,100,31,92,13,92,25,27,48,63,32,16,94,95,62,17,1,68,43,44,47,4,100,39,22,65,13,74,41,74,29,78,12,64,64,25,2,55,9,49,74,77,87,71,98,82,82,83,10,15,68,43,88,90,35,64,6,1,26,13,73,18,59,57,80,35,1,5,96,19,95,30,61,3,98,50,44,84,18,14}

    Returns: 771563453

  26. 7356

    {97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,17,68,18,85,29,25,13,34,70,18}

    {72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,72,49,86,64,1,20,98,83,96,43,77}

    Returns: 463466649

  27. 8563

    {97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,97,28,77,98,82,100,4,44,14,18,68}

    {12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,98,4,3,43,35,52,84,7,44,88}

    Returns: 435201566

  28. 1815

    {23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,29,41,86,94,20,93,74,62,62,75}

    {30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,32,84,27,3,82,59,81,35,45,86}

    Returns: 392570469

  29. 11540

    {77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,77,55,9,2,47,70,51,9,79,65,89}

    {60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,66,91,3,30,52,34,75,15,33,38}

    Returns: 435703488

  30. 256

    {4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,14,17,70,88,48,51,67,75,92,40}

    {5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,52,20,69,11,54,37,51,40,5,33}

    Returns: 831925175

  31. 3877

    {96,92,7,41,48,44,99,3,42,97,4,49,43,3,2,8,99,93,95,4,99,43,45,48,95,3,46,10,10,98,42,7,42,2,46,7,42,49,93,93,2,2,43,3,7,91,97,94,99,93,45,91,44,43,99,42,4,41,95,7,49,99,5,49,44,94,47,94,5,47,4,6,6,94,10,50,44,43,46,5,8,41,45,10,48,41,99,95,97,5,47,98,41,47,96,48,100,3,91,1}

    {96,3,10,41,46,45,46,42,91,43,43,91,8,7,92,99,41,95,94,48,98,45,43,47,48,45,95,99,46,96,44,97,95,99,7,46,10,4,4,2,91,99,43,42,47,91,94,92,96,97,92,43,5,100,49,2,50,41,46,43,7,98,97,41,96,92,96,97,94,3,9,4,92,3,9,5,42,47,91,8,94,96,10,96,47,6,2,92,6,44,99,100,1,1,4,43,100,48,48,42}

    Returns: 683157751

  32. 3994

    {99,46,96,6,7,43,46,95,98,48,92,1,6,4,44,5,44,42,98,45,3,91,5,3,97,91,47,46,93,42,92,9,98,7,1,7,97,7,47,45,42,99,46,48,6,41,4,7,98,1,100,3,8,98,7,6,41,43,98,44,6,43,48,41,97,7,92,8,3,8,7,49,3,92,92,97,3,100,5,43,46,96,100,46,7,45,7,7,91,7,92,92,42,8,96,93,3,46,94,8}

    {98,100,42,97,6,91,10,100,41,4,95,48,49,46,42,10,43,92,96,92,10,3,96,2,10,98,3,48,94,49,45,7,6,50,100,5,92,50,93,41,99,45,98,44,1,10,49,93,97,3,9,49,50,94,43,94,44,97,3,43,10,98,100,97,96,47,44,1,100,92,46,42,8,41,6,2,100,95,7,43,43,2,50,41,50,8,48,99,2,96,2,10,5,2,45,96,48,48,91,93}

    Returns: 137255908

  33. 4902

    {98,5,97,44,2,100,5,41,41,46,47,98,96,50,5,98,5,98,98,5,5,97,94,6,7,94,4,4,92,43,97,44,46,1,99,44,50,42,42,5,6,7,94,48,49,9,49,96,42,8,46,48,94,47,91,43,47,48,3,98,96,91,46,92,5,91,94,46,96,2,41,41,9,95,5,10,1,96,1,97,100,1,1,94,93,46,46,3,99,50,45,99,1,46,91,97,5,45,96,3}

    {98,45,1,3,42,9,98,42,3,8,46,8,9,94,50,49,94,92,95,50,96,49,97,99,46,1,50,95,10,5,49,6,47,7,45,6,1,47,2,42,4,41,93,50,8,6,10,92,46,4,5,97,91,97,10,50,1,50,4,9,46,9,4,44,100,93,7,49,47,43,45,10,44,45,42,4,2,50,6,98,5,44,10,97,95,43,41,41,100,44,98,50,2,97,98,45,6,4,1,3}

    Returns: 88374856

  34. 5453

    {91,50,3,44,46,2,2,10,3,2,9,9,100,97,50,44,93,41,5,94,50,5,4,48,95,92,95,46,8,47,4,3,96,44,3,8,48,1,98,92,10,4,45,49,7,46,92,94,48,1,6,91,42,93,43,48,92,94,94,50,96,93,46,46,1,9,8,96,9,48,99,92,98,9,99,41,47,99,98,7,47,94,94,50,96,47,10,42,97,97,98,6,97,9,95,95,92,45,1,47}

    {8,1,99,92,47,45,8,97,44,95,43,42,100,46,93,2,92,4,97,91,46,4,6,44,7,10,99,1,6,6,97,96,46,95,97,1,93,41,9,48,50,5,4,47,92,9,8,5,92,95,1,98,92,45,91,10,46,98,4,91,94,99,41,9,41,4,96,50,3,42,93,42,91,97,45,9,47,43,95,4,4,49,49,8,95,1,47,45,4,49,92,100,99,8,41,1,49,44,92,96}

    Returns: 463966095

  35. 587

    {10,97,5,98,48,2,9,42,97,41,42,9,45,92,96,46,9,4,10,4,50,10,8,47,8,92,47,41,48,43,1,46,1,91,2,6,3,92,50,44,5,9,49,1,9,95,42,95,5,45,1,47,92,5,1,100,1,50,91,1,1,95,94,3,9,49,98,42,95,3,93,100,95,2,47,6,47,6,5,97,100,6,41,2,46,94,8,91,98,44,91,5,94,94,46,46,4,4,41,5}

    {95,44,4,3,1,97,47,5,5,42,45,97,44,98,97,50,10,91,10,41,95,4,10,97,48,100,7,98,99,93,43,42,9,3,48,2,45,3,45,49,99,45,7,48,97,45,2,97,96,9,50,48,10,49,92,45,49,99,44,96,49,5,93,92,1,5,97,8,41,6,98,93,2,92,6,3,10,45,41,49,91,100,7,45,99,42,92,41,94,98,9,92,98,50,8,9,100,44,42,49}

    Returns: 778933645

  36. 9988

    {30,29,70,27,82,55,12,78,62,95,65,37,68,81,71,54,11,2,55,37,89,84,90,2,75,97,59,72,92,1,60,51,61,95,69,67,55,100,16,82,80,81,69,63,3,17,98,14,66,88,38,51,96,65,56,20,13,74,53,50,88,80,62,40,94,34,44,32,86,23,97,77,57,60,7,15,11,11,63,48,26,6,94,29,86,61,8,11,74,53,8,56,53,15,31,46,20,51,68,53}

    {91,53,5,33,42,29,56,18,54,71,61,51,54,62,18,85,61,50,8,50,42,46,2,26,87,73,55,26,6,100,8,72,57,90,44,86,51,55,5,39,13,30,30,14,8,78,89,39,47,1,67,25,22,24,36,46,34,97,81,74,16,66,44,61,29,22,50,10,1,45,39,44,34,51,28,8,83,95,92,28,51,55,65,17,15,19,84,84,61,6,78,52,83,83,58,3,92,28,91,37}

    Returns: 395351692

  37. 9256

    {90,79,79,13,92,69,67,95,99,99,7,79,28,1,11,7,61,34,46,49,48,89,7,63,48,56,62,47,58,5,71,87,3,58,91,37,37,81,69,36,59,66,62,20,96,58,46,42,26,69,77,59,27,61,84,26,68,85,95,14,25,22,93,6,55,25,19,70,31,92,99,97,9,62,21,38,30,64,44,61,41,100,30,95,66,95,32,40,58,32,34,1,47,38,84,31,43,77,2,58}

    {75,50,38,55,16,83,97,96,31,2,51,56,59,90,73,77,52,22,48,30,54,76,45,77,11,1,23,91,32,13,54,80,41,28,22,12,77,78,93,4,75,57,49,26,30,38,61,60,13,28,8,42,3,14,81,46,78,32,42,52,79,7,53,13,6,73,47,20,55,58,29,65,96,85,55,95,26,81,6,79,23,11,56,37,17,59,4,75,10,96,19,47,20,61,78,72,32,77,41,52}

    Returns: 319080077

  38. 9390

    {21,39,44,23,67,29,55,38,60,35,81,7,29,81,53,68,92,96,46,91,45,62,16,2,11,27,32,66,48,94,6,33,29,28,52,99,15,90,58,66,27,4,88,52,34,20,93,29,42,98,81,97,11,53,40,5,35,69,33,8,75,16,58,1,53,21,84,9,19,63,73,15,62,11,12,90,54,56,91,91,13,51,19,13,30,26,13,79,4,2,53,39,74,33,88,20,47,27,59,35}

    {16,67,66,2,55,100,8,97,3,75,32,28,51,76,40,53,82,94,65,98,93,95,65,85,4,38,46,83,59,59,4,11,90,49,16,43,69,51,28,12,80,17,76,3,53,27,41,100,5,51,50,73,33,28,47,23,61,4,18,98,15,14,67,10,8,48,95,66,5,10,28,36,31,66,89,62,76,37,86,3,73,68,52,83,35,59,49,67,12,91,2,70,83,2,1,46,70,57,45,96}

    Returns: 850390503

  39. 10347

    {29,6,91,48,5,99,47,49,17,86,69,21,100,82,52,42,57,74,70,99,2,99,29,93,56,6,40,51,35,83,34,57,52,92,63,42,99,34,74,58,39,53,4,7,25,20,4,45,94,84,59,75,28,52,4,16,30,14,86,79,94,52,41,44,22,77,19,73,38,3,52,74,18,57,48,100,13,58,25,60,65,62,13,29,42,88,97,72,77,37,69,46,4,4,61,93,56,79,74,79}

    {86,58,52,46,52,99,67,70,25,88,70,39,97,77,67,30,92,2,97,87,32,53,26,2,2,55,33,30,66,61,79,87,69,5,52,61,30,92,77,88,53,97,41,41,8,85,25,52,21,80,17,8,22,79,73,20,100,92,60,52,27,79,97,3,12,48,28,74,8,26,49,36,43,13,53,99,74,73,84,100,78,10,38,39,83,74,14,42,49,87,67,19,47,91,8,54,12,37,17,19}

    Returns: 223805344

  40. 9306

    {66,20,28,9,21,89,7,45,75,97,93,45,65,71,2,49,86,92,83,48,97,93,9,69,50,4,47,88,7,91,17,78,35,48,72,12,43,31,62,59,48,32,28,81,84,46,92,7,38,99,36,2,21,60,14,6,57,17,83,97,23,4,87,80,16,71,9,5,57,41,17,24,4,12,44,71,33,57,38,71,37,38,56,58,62,40,53,39,17,9,72,40,64,78,52,76,79,37,93,62}

    {88,8,84,42,61,64,70,70,21,84,63,100,64,93,74,18,10,30,65,18,26,84,52,44,14,2,68,100,74,6,90,59,74,39,11,78,66,87,4,90,55,63,38,88,14,43,26,40,67,66,74,90,87,56,39,81,98,22,25,84,55,68,37,32,14,14,37,11,86,100,21,23,83,7,73,63,19,61,54,23,6,45,30,30,60,50,33,3,96,4,59,10,34,29,69,25,48,67,78,98}

    Returns: 950372925

  41. 7799

    {47,25,1,49,72,49,24,97,23,70,74,71,75,73,23,1,25,70,72,49,5,50,2,100,100,5,96,24,22,96,46,48,50,98,48,25,2,23,74,73,46,1,49,73,74,72,24,45,23,74,96,98,25,47,48,100,1,21,22,97,50,70,24,73,3,99,95,49,49,50,98,100,25,72,70,2,24,25,1,21,2,25,74,22,75,1,4,96,5,49,4,24,21,21,23,72,5,48,21,96}

    {3,4,97,73,75,1,73,23,24,72,3,2,23,71,3,2,70,97,50,73,4,4,3,75,2,2,97,25,49,46,74,25,2,48,3,96,74,22,45,49,75,72,46,100,22,45,46,100,2,23,75,22,3,96,4,46,21,72,25,99,72,95,2,71,74,50,3,25,100,70,75,75,5,22,4,4,50,99,100,1,5,4,98,71,48,97,46,50,4,4,4,3,47,1,73,3,5,99,5,71}

    Returns: 314079980

  42. 2786

    {46,99,4,25,21,73,3,3,47,1,97,4,47,75,4,47,98,22,1,74,45,96,22,48,45,73,73,50,23,49,98,98,23,71,73,45,100,4,98,25,4,73,50,24,50,22,72,21,3,1,4,1,46,99,48,95,4,25,5,73,3,70,21,75,98,46,98,46,97,2,71,96,23,45,98,23,73,100,99,2,70,5,47,21,75,24,49,1,73,73,75,1,5,5,98,48,97,48,100,50}

    {47,1,3,71,21,98,96,4,25,25,50,24,46,45,22,21,22,24,5,25,73,98,3,24,21,25,22,22,96,25,74,50,99,49,49,96,46,49,74,24,46,97,98,2,71,23,1,46,99,72,3,3,25,4,22,1,50,72,99,99,24,22,46,98,50,73,3,100,96,4,71,99,49,25,2,3,74,25,2,24,21,4,5,4,23,50,95,4,1,75,23,24,22,96,25,74,47,5,98,22}

    Returns: 307626415

  43. 8610

    {5,48,71,72,4,22,50,95,50,1,3,71,98,48,21,21,45,50,72,100,45,97,22,100,73,2,49,97,3,50,46,47,74,22,46,25,72,25,25,4,50,5,46,49,74,45,2,47,50,24,46,50,5,4,24,95,72,73,96,74,71,70,75,50,4,25,4,45,95,95,98,21,100,75,25,74,21,99,74,95,24,97,24,75,5,21,74,70,96,47,22,99,24,48,73,98,25,3,98,3}

    {98,5,3,50,75,96,25,95,95,72,24,4,99,3,96,100,21,24,100,97,1,49,70,22,95,3,5,74,71,96,95,95,47,24,95,4,23,98,73,22,5,50,21,50,99,24,21,21,24,21,21,25,47,25,99,73,50,97,73,22,46,48,96,74,3,97,22,1,100,47,97,46,99,96,98,24,95,24,2,22,97,99,98,74,25,45,49,23,5,25,22,22,100,21,48,24,95,99,98,47}

    Returns: 976962315

  44. 6203

    {3,4,97,21,98,22,95,21,1,1,96,98,48,96,75,22,24,21,99,25,71,22,48,23,21,70,97,21,99,3,25,25,98,46,97,25,2,45,23,73,5,45,5,47,4,25,47,22,21,72,71,75,23,1,4,75,23,71,98,47,23,24,24,70,47,48,49,2,22,97,21,71,75,99,1,46,70,45,98,24,45,45,21,72,95,3,96,5,3,2,97,23,99,98,99,25,100,75,46,21}

    {75,72,23,74,74,50,50,4,21,50,45,74,97,71,47,50,46,95,71,3,95,99,72,95,75,2,24,48,73,1,47,2,98,22,23,24,75,98,24,72,25,50,95,22,75,5,72,21,23,2,75,100,74,97,24,46,48,49,97,100,4,95,5,50,71,100,70,45,22,24,1,2,25,70,3,70,49,2,70,4,99,99,49,96,1,48,95,97,70,45,3,5,72,47,96,3,25,99,2,72}

    Returns: 220423797

  45. 5536

    {45,46,70,5,70,22,48,25,3,23,24,70,4,21,46,45,46,24,2,98,3,22,98,48,47,70,3,73,25,4,24,98,3,97,72,50,98,74,98,73,24,98,24,100,24,4,2,95,25,97,22,48,5,99,25,3,98,98,99,47,100,22,75,71,97,25,97,47,97,48,73,4,95,72,5,50,48,2,71,1,4,22,5,97,99,47,70,4,71,97,1,99,48,73,74,22,1,21,21,96}

    {4,47,74,97,47,21,1,75,98,5,22,75,2,22,99,5,46,2,74,75,5,25,21,71,1,24,2,74,49,24,1,70,47,73,74,23,5,50,45,96,97,5,47,74,24,74,24,99,46,24,23,21,99,45,24,21,96,73,22,4,49,4,98,100,22,96,48,75,3,74,73,25,96,74,48,48,3,5,3,2,21,24,72,74,50,49,2,75,72,72,45,25,72,1,4,74,72,99,24,22}

    Returns: 825412182

  46. 11460

    {48,22,4,96,98,99,100,22,99,22,3,2,22,71,71,97,98,96,99,48,23,1,45,22,74,95,97,99,73,2,45,1,2,23,95,75,2,5,99,23,97,48,96,50,96,50,98,1,98,97,25,95,100,99,24,1,74,24,74,71,73,24,25,74,4,96,5,4,96,47,25,70,49,98,50,99,24,98,24,99,49,74,48,97,24,98,23,95,45,73,25,50,48,74,98,96,48,2,48,3}

    {99,74,96,24,71,100,24,48,74,2,97,21,50,46,70,50,5,22,95,47,72,25,70,100,1,96,70,100,70,97,23,72,73,4,45,73,24,46,5,1,70,99,24,99,4,47,22,1,95,5,49,99,45,96,71,73,4,100,99,47,48,97,23,5,99,48,97,5,95,100,49,49,47,47,95,97,95,98,46,25,98,1,100,73,24,95,97,21,49,98,99,21,99,3,74,21,99,95,100,100}

    Returns: 304211498

  47. 10566

    {95,98,99,95,49,25,2,3,2,24,98,3,75,48,98,97,24,97,2,98,5,47,24,50,23,70,1,23,72,100,95,4,2,96,46,23,48,99,23,98,45,97,47,25,98,4,23,5,2,95,2,23,75,98,97,72,95,47,99,96,48,22,4,96,24,99,95,21,22,23,46,97,47,21,95,73,25,4,98,99,73,73,74,1,4,96,97,98,48,75,96,2,23,1,45,72,100,75,97,95}

    {97,95,2,98,96,96,23,96,1,96,5,2,50,72,99,72,97,48,74,100,95,3,25,100,5,98,48,48,23,95,97,95,99,5,99,72,4,3,98,5,46,100,2,49,75,95,73,2,25,98,46,95,97,50,71,70,97,48,100,98,2,24,99,99,71,1,97,72,4,25,2,45,5,73,100,71,22,47,99,24,23,45,74,21,1,4,23,97,25,75,100,99,22,46,22,1,100,24,5,4}

    Returns: 964552166

  48. 10188

    {22,98,47,97,100,97,96,45,4,1,71,2,4,98,2,25,75,47,22,71,73,47,3,24,71,24,99,73,96,70,48,95,23,99,23,48,2,22,5,98,100,99,25,46,50,74,99,3,95,97,23,100,49,49,49,3,72,99,5,95,74,96,25,23,49,46,22,21,70,99,3,47,71,49,95,46,22,3,24,23,46,5,73,1,22,1,96,49,75,2,3,2,74,99,22,100,2,25,71,98}

    {96,45,45,75,73,22,97,97,73,96,50,100,45,25,71,97,25,4,72,99,70,5,4,4,72,2,21,75,97,98,96,98,72,98,25,5,97,100,100,50,48,97,73,24,3,97,22,72,1,24,25,72,3,96,49,71,75,48,24,24,72,50,23,100,46,98,49,2,45,48,48,21,99,48,75,100,73,97,45,5,3,95,71,2,50,96,74,100,70,100,73,95,23,98,98,25,97,24,74,75}

    Returns: 39434054

  49. 10013

    {15,45,81,24,72,43,12,33,45,100,99,21,54,51,99,10,10,77,40,97,47,95,8,72,73,8,77,18,40,87,93,85,26,77,50,63,23,21,1,28,8,46,52,80,27,83,42,88,70,77,96,36,9,18,49,73,49,89,100,86,99,8,32,46,93,49,64,1,35,30,100,20,26,19,1,6,50,15,45,12,8,10,78,65,6,15,80,58,25,73,15,14,97,45,7,22,64,21,35,57}

    {69,56,43,67,22,74,70,60,68,6,13,43,95,68,4,74,87,44,17,62,29,13,53,60,60,83,85,96,50,2,53,3,53,27,17,31,71,2,65,53,24,18,12,100,8,66,80,6,77,10,56,52,85,66,98,60,55,16,78,66,85,7,31,71,39,63,85,19,32,88,59,92,67,52,56,82,94,57,82,91,58,82,42,97,37,80,69,47,81,69,11,76,57,20,25,5,70,23,1,86}

    Returns: 240290891

  50. 9561

    {99,84,12,60,38,47,12,6,55,99,51,44,22,3,96,37,83,34,6,87,3,34,75,65,82,81,87,27,32,34,77,70,2,2,60,90,96,81,82,94,73,25,97,64,67,51,45,29,100,8,55,61,28,20,28,29,28,39,15,83,80,44,38,25,50,42,3,71,31,89,97,80,90,71,79,54,58,18,39,57,41,26,15,5,35,5,80,46,55,56,66,9,29,56,17,54,34,96,49,44}

    {18,11,94,82,25,23,11,68,36,60,55,34,67,60,22,30,21,22,45,58,15,86,20,55,91,76,90,91,22,22,20,54,9,79,59,84,43,30,100,28,7,52,42,4,13,39,63,87,15,55,49,18,7,8,10,15,14,61,38,66,16,72,80,20,75,95,97,84,2,71,38,12,54,3,56,27,95,91,64,6,24,35,52,59,19,4,36,38,60,9,47,9,57,86,65,18,28,60,96,94}

    Returns: 240290891

  51. 4

    {1,1,1,1}

    {1,1,1,1}

    Returns: 576

    Each of the (N!)^2 ways to permute the two sequences is counted separately, even if different permutations produce the same sequences of numbers.

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: