### Problem Statement

You work at a company specializing in internet-related technologies, and your current project is a spam filter. This filter determines whether or not a string contains spam-like information using a "spam-words-dictionary" (SWD). If an input string contains at least one word from this dictionary as a substring, the filter considers it to be spam-suspicious. (Note: an entire string is considered a substring of itself.)

You've decided to solve a more challenging problem: how many unique strings of length n, composed entirely of lowercase letters, are spam-suspicious for a given SWD? You are given a String[] dictionary, each element of which is a word from the SWD, and an int n. Return the answer modulo 10000.

### Definition

 Class: SuspiciousStrings Method: getAmount Parameters: String[], int Returns: int Method signature: int getAmount(String[] dictionary, int n) (be sure your method is public)

### Notes

-"Substring" is formed of consecutive letters (so, it's NOT a subsequence of letters).
-"x modulo y" means the remainder of x divided by y.

### Constraints

-dictionary will contain between 1 and 10 elements, inclusive.
-Each element of dictionary will contatin only lowercase letters ('a'-'z').
-Each element of dictionary will contain between 1 and 10 characters, inclusive.
-n will be between 1 and 2147483647, inclusive.

### Examples

0)

 `{"x"}` `1`
`Returns: 1`
 All one character length strings are allowed except for "x".
1)

 `{"ab","bb"}` `2`
`Returns: 2`
 Suspicious strings are "ab" and "bb".
2)

 `{"ab","bb"}` `5`
`Returns: 6350`
3)

 `{"aab","bba"}` `5`
`Returns: 4054`
4)

 `{"xxxxxx","xxx","x","yyxyy","xxxyxxx","y","yx","xy","zzzzzzzzzz"}` `5`
`Returns: 8752`
5)

 ```{"aaaaaaaaaa", "bbbbbbbbbb", "cccccccccc", "dddddddddd", "eeeeeeeeee", "ffffffffff", "gggggggggg", "hhhhhhhhhh", "xxxxxxxxxx", "zzzzzzzzzz"}``` `2147483647`
`Returns: 5040`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5966

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8080&pm=5966

gevak

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Dynamic Programming, String Manipulation