Coding questions · Uber

Count paths with prime-ending jumps

This question evaluates a candidate's ability to design and implement dynamic programming for counting paths, combining combinatorial reasoning with modular arithmetic and handling step-size constraints tied to primes ending in digit 3.

You are given an integer n representing the top of a staircase, where you start at step 0 and want to land exactly on step n.

In one move, you may jump:

exactly 1 step, or
any prime number of steps whose decimal representation ends with the digit 3 (for example: 3, 13, 23, 43).

Count how many distinct sequences of jumps allow you to reach step n exactly. Since the answer can be large, return it modulo 1,000,000,007.

A dynamic programming solution is expected. You may assume 1 <= n <= 100000.

Count Paths with Prime-Ending Jumps

Count sequences from step 0 to n using jumps of 1 or prime lengths ending in digit 3, modulo 1e9+7.

Examples

Example 1

Input: (3,)
Output: 2

Explanation: Either 1+1+1 or 3.

Example 2

Input: (5,)
Output: 4

Explanation: Prime-ending jump 3 plus ones.

Hints

Choose a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.