Бүтін \(n\) саны берілген. Ұзындықтарының қосындысы \(n\) болатын баспалдақпен секірудің барлық нұсқаларын шығару керек.

Бір секірісте дәл \(1\), \(2\) немесе \(4\) баспалдаққа көтерілуге болады. Секірістердің реті маңызды.

Жауапты кез-келген ретпен шығарыңыз.

Енгізу

Жалғыз жолда бүтін \(n\) саны берілген (\(1 \le n \le 20\)).

Шығару

Барлық секіру нұсқаларын шығарыңыз. Әр жолдағы секіріс ұзындықтары бос орынсыз қатар жазылады.

Мысалдар

Енгізу 1

4

Жауап 1

1111
112
121
211
22
4