The Travels of the Gnomes#400
As is known, dwarves lived in the forest and seldom traveled, moving mostly on foot. However, they built their own subway long before people did and used it exclusively for long journeys.
Travel was time-consuming, and subway tickets were quite expensive. However, they agreed that any dwarf who received a lucky ticket would get it for free. A ticket was considered lucky by the dwarves if, in the -ary numeral system, the sum of the first digits equals the sum of the last digits. It is known that subway ticket numbers among the dwarves always consist of digits.
How many dwarves, in this case, can travel for free on the subway? Note that the dwarves are very fair, and if one of them already had a free ride, they always gave the next lucky ticket to another companion.
A single line contains the values and separated by a space.
Output the sought number of dwarves, computed modulo .
Constraints
The dwarves secretly reported that, during a trip to Bucharest via Lviv, they learned about the lucky Lviv number , and now the numeral system and ticket numbers are such that k\,(p-1) + 1 \leq 4444.
Example 1