Even and Prime Digit Codes

Medium

A code is a string of digits 0–9; leading zeros are allowed. Positions are numbered from zero. A code is **valid** if every even position holds an even digit (0, 2, 4, 6, 8) and every odd position holds a prime digit (2, 3, 5, 7). For example, "4382" is valid, but "5222" is not: position 0 holds the odd digit 5. Return the number of valid codes of length length, modulo 10⁹ + 7.

Example 1

length=2 → 20

Position 0 takes one of 5 even digits, position 1 one of 4 primes: 5·4 = 20.

Example 2

length=3 → 100

One more even position is added: 20·5 = 100.

Example 3

length=1 → 5

Constraints

1 ≤ length ≤ 10¹⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion Math

Similar problems

Adding Digit Lists Medium Fast Exponentiation Medium Every Bracketing Result Medium Last One After the Sweeps Medium Duel for the End Cards Medium

Input

length=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 6 tests on the server, hidden ones included.