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