Travel Itinerary Combinations

You are planning a journey of 7000 km. Along the route, there are motels whose positions (in km from the starting point) are given by the preset list:

\( [0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000] \)

Before departure, additional motels may be added. After merging the two sets (the preset list and any additional motels) and sorting them (keeping unique positions), you must plan your stops so that:

• Each day you travel at least \( A \) km.
• Each day you travel at most \( B \) km.

You always start at 0 km and must finish at 7000 km. Determine the number of valid travel itineraries (i.e. sequences of motels) such that the distance between any two consecutive motels is between \( A \) and \( B \) (inclusive).

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \( A \) and \( B \) representing the minimum and maximum daily travel distance.
2. The second line contains an integer \( n \), the number of additional motels.
3. The third line (if \( n \gt 0 \)) contains \( n \) integers, representing the positions of the additional motels.

The preset motel positions (which are always available) are:

\( 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000 \)

outputFormat

Output a single integer: the number of valid travel itineraries from 0 km to 7000 km that satisfy the daily travel constraints.

sample

500 1500
0

168