Перестановка цифр
Исполнитель преобразует целое число на экране. A прибавляет 1. B меняет местами цифры десятков и единиц, только если цифра десятков меньше цифры единиц.
Найдите число программ, переводящих A в B.
Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Входные данные
Два целых числа A и B: 100 ≤ A ≤ B ≤ 199.
Выходные данные
Выведите одно целое число — количество подходящих программ. Если таких программ нет, выведите 0.
Примеры
100 141
16
101 110
2
Примечание
Чтобы не потерять программы, разделим их по первой перестановке. До неё идут только прибавления, поэтому число перед первым B однозначно задаёт начало программы. В таблице перечислены все допустимые первые перестановки; правый столбец — число продолжений до 141 после неё. Ещё одна программа состоит только из 41 прибавления. Складываем: 1 + 6 + 2 + 1 + 1 + 2 + 1 + 1 + 1 = 16.
Например, первая перестановка в 101 даёт 110, а из 110 до 141 есть шесть продолжений. Перестановка в 104 даёт 140: дальше остаётся единственное прибавление. Для второго примера, 101 → 110, есть две программы: девять прибавлений и одна перестановка.
| Перед первым B | После B | Продолжений до 141 |
|---|---|---|
| Без B | 41 прибавление | 1 |
| 101 | 110 | 6 |
| 102 | 120 | 2 |
| 103 | 130 | 1 |
| 104 | 140 | 1 |
| 112 | 121 | 2 |
| 113 | 131 | 1 |
| 114 | 141 | 1 |
| 123 | 132 | 1 |