Во всех школах Бурятии в \(1\) классе всем рассказывают теорию фибоначчиевых строк.
«Блок — это подотрезок строки, все буквы которого одинаковы, а слева и справа он ограничен концами строки или отличными от букв в блоке буквами. Строка называется фибоначчиевой, если при разбиении её на блоки их длины в порядке следования в строке составляют последовательность чисел Фибоначчи (\(f_0 = f_1 = 1\), \(f_i = f_{i-2} + f_{i-1}\)), начиная с нулевого члена последовательности. Строка называется полуфибоначчиевой, если хотя бы одна из перестановок её букв является фибоначчиевой строкой.»
Бурёнка решила поступать в Бурятский государственный университет, но на вступительном экзамене ей дали непростую задачу. Ей дали строку, состоящую из букв бурятского алфавита (в котором ровно \(k\) букв), и спросили, является ли данная ей строка полуфибоначчиевой. Так как строка могла быть очень длинной, ей сообщили только число вхождений каждой буквы алфавита (\(c_i\) для \(i\)-й буквы) в эту строку. К сожалению, Бурёнка уже не помнит теорию фибоначчиевых строк, поэтому без вашей помощи она не поступит в университет.
Выходные данные
Для каждого набора входных данных выведите строку «YES», если соответствующая строка является полуфибоначчиевой, и «NO», если не является.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», «Yes» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных строка из одного символа является полуфибоначчиевой, являясь сама по себе фибоначчиевой строкой.
Во втором наборе входных данных строка из двух различных символов является фибоначчиевой.
В третьем наборе входных данных строка «abb» (пусть первая буква — a, вторая — b) не является полуфибоначчиевой строкой, так как все перестановки её букв («abb», «bab» и «bba») не являются фибоначчиевыми строками.
В четвёртом наборе входных данных две перестановки букв строки «abaccac» (первая буква — a, вторая — b, третья — c) являются фибоначчиевыми строками — «abaaccc» и «cbccaaa».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
1
2
1 1
2
1 2
3
3 1 3
2
7 5
6
26 8 3 4 13 34
|
YES
YES
NO
YES
NO
YES
|