Statistics

Problem Statement for "MappingABC2"

Problem Statement

The lotteries you know are probably quite boring. You just buy a lottery ticket with some numbers and then you hope that the organizers announce the same set of numbers. As you will discover below, the lottery in Bearland is way more fun!


In the Bearland lottery, you win if you have a ticket that matches the goal string. The goal string is a string of length N chosen by the organizers. Each character of the string will be 'A', 'B', or 'C'. Additionally, it is guaranteed that the goal string will contain "ABC" as a subsequence. For example, "AABAC" and "BBABC" are two possible goal strings of length 5, but "CBAAA" is not a goal string.


However, the lottery tickets do not contain any strings at all. Instead, each Bearland lottery ticket contains some sequence of N (not necessarily distinct) integers.


You win the lottery if you can transform your sequence into the goal string. Transformation rules:

  • Each element of the sequence should be replaced by a single character: 'A', 'B', or 'C'.
  • All occurrences of the same number must be replaced by the same letter.


For example, the sequence {5, 8, 5, 2} can be transformed into "ABAC" or "BABB" but not into "ABBB".


Limak got a lottery ticket for his birthday. You are given the int[] t: the sequence of the N numbers on the the ticket. Count the number of different goal strings for which Limak can win the lottery. Return that count modulo 10^9+7.

Definition

Class:
MappingABC2
Method:
countStrings
Parameters:
int[]
Returns:
int
Method signature:
int countStrings(int[] t)
(be sure your method is public)

Constraints

  • t will have exactly N elements.
  • N will be between 3 and 50, inclusive.
  • Each element in t will be between 1 and 50, inclusive.

Examples

  1. {9,9,2,9,4}

    Returns: 2

    Limak can transform this lottery ticket into 27 different strings. Some of them are: AAAAA, AAAAB, AAAAC, AABAA, AACAA, AABAB, AABAC, AACAB, AACAC, BBABA, BBABB, ... Among them, only two strings are valid goal strings: AABAC and BBABC. Thus, the answer is 2.

  2. {1,2,3}

    Returns: 1

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

    Returns: 0

  4. {7,50,1,50,1,50,1,10,7}

    Returns: 20

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

    Returns: 166952139

  6. {1,1,1}

    Returns: 0

  7. {50,50,50}

    Returns: 0

  8. {50,49,48}

    Returns: 1

  9. {1,2,1}

    Returns: 0

  10. {2,2,1}

    Returns: 0

  11. {1,4,6,10}

    Returns: 9

  12. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

    Returns: 0

  13. {1,1,1,7,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

    Returns: 2

  14. {1,1,1,7,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,10}

    Returns: 13

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

    Returns: 280204150

  16. {1,2,3,4,5,50,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,45,46,47,48,49,50}

    Returns: 817552375

  17. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 0

  18. {20,18,44,7,12,43,30,24,22,20,35,38,49,25,16,21,14,27,42,31,7,24,13,21,47,32,6,26,35,28,37,6,47,30,14,8,25,46,33,46,15,18,35,15,44,1,38,9,27,29}

    Returns: 443792788

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

    Returns: 14236179

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

    Returns: 1806

  21. {6,3,10,2,9,11,15,8,1,14,9,9,4,7,4,10,12,5,14,14,9,9,12,11,5,14,4,4,10,13,3,7,15,4,1,9,6,15,8,6,5,1,6,15,15,2,10,3,13,15}

    Returns: 14250501

  22. {6,3,10,2,9,11,15,8,1,14,9,9,4,7,4,10,12,5,14,14,9,9,12,11,5,14,4,4,10,13,3,7,15,4,1,9,6,15,8,6,5,1,6,15,15,2,10,3,13}

    Returns: 14250501

  23. {15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

    Returns: 1

  24. {1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3}

    Returns: 5

  25. {1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,20,3,3,3,3,3,3,3,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3}

    Returns: 32

  26. {1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1}

    Returns: 4

  27. {1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,20,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1}

    Returns: 28

  28. {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, 45, 46, 47, 48 }

    Returns: 166952139

  29. {9, 9, 2, 9, 4 }

    Returns: 2

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

    Returns: 280204150

  31. {7, 50, 1, 50, 1, 50, 1, 10, 7 }

    Returns: 20

  32. {1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 8, 9, 10, 50, 34, 34, 35, 36, 37, 38, 39, 20, 21, 21, 22, 23, 21, 24, 21, 12, 12, 12, 13, 1, 2, 3, 4, 15, 5, 6, 20, 14 }

    Returns: 474888302

  33. {1, 2, 3, 4 }

    Returns: 9

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: