На день рождения Ntarsis получил два целых числа \(n\) и \(k\). Он задался вопросом, сколько фибоначчи-подобных последовательностей длины \(k\) можно сформировать таким образом, чтобы \(n\) было \(k\)-м элементом последовательности.
Последовательность неубывающих неотрицательных целых чисел считается фибоначчи-подобной, если \(f_i = f_{i-1} + f_{i-2}\) для всех \(i > 2\), где \(f_i\) обозначает \(i\)-й элемент последовательности. Обратите внимание, что \(f_1\) и \(f_2\) могут быть произвольными.
Например, последовательности \([4,5,9,14]\) и \([0,1,1]\) считаются допустимыми, в то время как \([0,0,0,1,1]\), \([1, 2, 1, 3]\) и \([-1,-1,-2]\) — нет: первые две не везде удовлетворяют \(f_i = f_{i-1} + f_{i-2}\), а последняя не выполняет условие, что элементы неотрицательны.
Произведите впечатление на Ntarsis, оказав ему помощь в решении этой задачи.
Выходные данные
Для каждого набора входных данных выведите одно число — количество допустимых фибоначчи-подобных последовательностей длины \(k\), в которых \(k\)-м элементом является \(n\). Иными словами, выведите количество последовательностей \(f\) из \(k\) элементов таких, что \(f\) — фибоначчи-подобная, и \(f_k = n\). Можно показать, что это число конечно.
Примечание
Для \(n = 22\), \(k = 4\) существует \(4\) допустимые фибоначчи-подобные последовательности:
- \([6,8,14,22]\)
- \([4,9,13,22]\)
- \([2,10,12,22]\)
- \([0,11,11,22]\)
Для \(n = 3\), \(k = 9\) можно показать, что не существует допустимой фибоначчи-подобной последовательности, удовлетворяющей данным условиям.
Для \(n = 55\), \(k = 11\), единственная подходящая фибоначчи-подобная последовательность это \([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
22 4
3 9
55 11
42069 6
69420 4
69 1434
1 3
1 4
|
4
0
1
1052
11571
0
1
0
|