Skip to main content
Back to problems
Leetcode
Medium
Math
Number Theory
Combinatorics
Bit Manipulation
Count Good Numbers

Count how many digit strings of length nn satisfy parity-based digit rules, modulo 109+710^9+7.

Acceptance 0%
Start Practice
Problem Statement

Problem

You are given a non-negative integer n.

A length-n digit string is considered good if it satisfies these rules:

  • Digits in even positions (0-indexed) must be chosen from {0, 2, 4, 6, 8}.
  • Digits in odd positions must be chosen from {2, 3, 5, 7}.

Return the number of good digit strings of length n, modulo 109+710^9 + 7.

The string may start with 0 if position 0 is even.

Notes

  • Positions are counted from left to right starting at 0.
  • You only need to count the valid strings; do not generate them explicitly.

Input Format

  • A single integer n representing the length of the digit string.

Output Format

  • Return one integer: the number of good digit strings of length n modulo 109+710^9 + 7.

Constraints

  • 0≤n≤10150 \le n \le 10^{15}
  • Answer must be computed modulo 109+710^9 + 7
Examples
Sample cases returned by the problem API.

Example 1

Input

n = 1

Output

5

Explanation

Only the even-position rule applies to the first character: {0,2,4,6,8} gives 5 possibilities.

Example 2

Input

n = 4

Output

400

Explanation

There are 2 even positions and 2 odd positions. The count is 52×42=4005^2 \times 4^2 = 400.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints
Editorial and discussion links
Concept map and variants
Sign in to unlock
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.
Sign in to track progress