Cerința

Scrieți un program care citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:

- încep şi se termină cu 0;
- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.
Astfel, pentru n=5, combinaţiile afişate sunt, în ordine, următoarele: 01010, 01210.

Date de intrare

Programul citește de la tastatură numărul n, impar.

Date de ieșire

Programul va afișa pe ecran, pe rânduri separate, soluțiile generate.

Restricții și precizări

• 3 ≤ n ≤ 19

Exemplu:

Intrare

5

Ieșire

01010 
01210