### Problem Statement

Given a positive integer N, let P(N) denote the product of all digits in the decimal representation of N. For example, P(4256) = 4 * 2 * 5 * 6 = 240, P(2112) = 2 * 1 * 1 * 2 = 4 and P(100) = 1 * 0 * 0 = 0.

Consider the infinite sequence S = (P(1), P(2), P(3), ...). Given a int[] prod containing exactly M elements, find the first occurrence of (prod[0], prod[1], ..., prod[M-1]) in S as a consecutive subsequence. In other words, return the smallest positive index X such that P(X + i) = prod[i] for all i between 0 and M-1, inclusive. The constraints will guarantee that at least one such X exists.

### Definition

 Class: ProductsOfDigits Method: firstOccurrence Parameters: int[] Returns: long Method signature: long firstOccurrence(int[] prod) (be sure your method is public)

### Notes

-It can be shown that under the constraints of this problem, the return value will always fit within a 64-bit signed integer datatype.

### Constraints

-prod will contain between 1 and 50 elements, inclusive.
-Each element of prod will be between 0 and 1,000,000,000, inclusive.
-There will be at least one occurrence of (prod[0], ..., prod[M-1]) in S as a consecutive subsequence, where M is the number of elements in prod.

### Examples

0)

 `{1, 2, 3, 4, 5}`
`Returns: 1`
 Since P(1) = 1, P(2) = 2, ..., P(5) = 5, we have that S starts with an occurrence of (1, 2, 3, 4, 5).
1)

 `{9, 0, 1}`
`Returns: 9`
 P(9) = 9, P(10) = 0, P(11) = 1.
2)

 `{0, 0, 0, 0}`
`Returns: 100`
 All numbers between 100 and 103, inclusive, have a 0 in their decimal representations.
3)

 `{288}`
`Returns: 489`
 4 * 8 * 9 = 288.
4)

 `{108864, 127008, 145152, 163296, 0, 22680, 45360, 68040, 90720}`
`Returns: 789946`
5)

 `{1}`
`Returns: 1`
6)

 `{0, 1, 2, 3, 4, 5}`
`Returns: 10`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14282&pm=11015

ivan_metelsky

#### Testers:

PabloGilberto , zhuzeyuan

#### Problem categories:

Dynamic Programming, Simple Math