### Problem Statement

John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.

A lucky sequence is a sequence of length numbers A, A, ..., A[length - 1] that satisfies all of the following properties:

• Each number A[i] is lucky, where 0 <= i < length.
• For each i, where 0 <= i < length, there exists at least one j such that A[i] = numbers[j].
• For each i, where 0 <= i < length - 1, the last digit of A[i] is the same as the first digit of A[i + 1].

You are given a int[] numbers and an int length. Return the number of distinct lucky sequences modulo 1234567891.

### Definition

 Class: TheLuckySequence Method: count Parameters: int[], int Returns: int Method signature: int count(int[] numbers, int length) (be sure your method is public)

### Notes

-Two lucky sequences A, A, ..., A[length - 1] and B, B, ..., B[length - 1] are considered distinct if there exists i, 0 <= i < length, such that A[i] ≠ B[i].

### Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will be between 1 and 1,000,000,000, inclusive.
-length will be between 1 and 1,000,000,000, inclusive.

### Examples

0)

 `{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}` `1`
`Returns: 2`
 There are only two lucky numbers among these ten integers.
1)

 `{47, 74, 47}` `3`
`Returns: 2`
 We can construct only two different sequences (47, 74, 47) and (74, 47, 74).
2)

 `{100, 4774, 200, 747, 300}` `47`
`Returns: 2`
3)

 `{44, 47, 74, 77}` `2`
`Returns: 8`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12175&pm=8569

Vasyl[alphacom]

#### Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Recursion