JOIN
Get Time

   Problem Statement  

 Problem Statement for MappingABC

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:MappingABC
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 3000, inclusive.
-Each element in t will be between 1 and 3000, inclusive.
 

Examples

0)
    
{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.
1)
    
{1,2,3}
Returns: 1
2)
    
{1,2,2,1,2,1,2}
Returns: 0
3)
    
{7,3000,1,3000,1,3000,1,10,7}
Returns: 20
4)
    
{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

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 706 Round 1 - Division I, Level Two