Ровно столько команд
Исполнитель преобразует целое число на экране. A прибавляет 1. B умножает на 2.
Найдите число программ из A в B, состоящих ровно из K команд.
Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Входные данные
Три целых числа A, B и K: 1 ≤ A ≤ B ≤ 1000, 0 ≤ K ≤ 20.
Выходные данные
Выведите одно целое число — количество подходящих программ. Если таких программ нет, выведите 0.
Примеры
1 4 2
2
1 4 3
2
Примечание
За две команды 1 превращается в 4 программами AB и BB. AAA тоже даёт 4, но состоит из трёх команд и здесь не учитывается. Для второго примера длина 3, поэтому подходят AAA и BAA: ответ снова 2.