Смуга#1537
Дан прямокутник розміру 1 \times n, розбитий на клітини 1 \times 1. Кожна клітина може бути зафарбована або в білий, або в чорний колір.
Кодом даного прямокутника називається послідовність чисел, кожне з яких дорівнює кількості поспіль чорних клітин при перегляді прямокутника зліва направо.
Наприклад, код для прямокутника, зображеного вище, дорівнює . Кількість білих клітин в коді не враховується; при цьому кожна група чорних клітин повинна бути відокремлена від наступної хоча б однією білою клітиною. Таким чином, одному і тому ж коду можуть відповідати кілька різних прямокутників. Зокрема, наступний прямокутник також має вказаний код:
Визначте кількість прямокутників, яким відповідає заданий код.
Перша строка містить кількість тестів t~(1 < t < 20). Кожен із наступних рядків є окремим тестом і містить:
довжину прямокутника n~(1 \le n \le 200);
кількість чисел в коді k~(0 \le k \le \frac{n+1}{2});
чисел, що описують код.
Для кожного тесту у окремому рядку виведіть кількість прямокутників, що відповідають даному коду.
Приклад 1