Коцки
Мими го слави својот седми роденден. Нејзините родители како подарок за роденденот и купиле коцки. Коцките имаат квадратна форма и истите се редат на долгнавеста плочка на која има N подножја за такви коцки. За фигура се смета секоја секвенца од минимум 3 соседни коцки поставени на плочката. Мими ги реди коцките на плочката формирајќи фигури. Фигурите се одделени со најмалку едно празно подножје.
Ваша задача е да напишете програма која ќе го пресмета бројот на различни начини на кои може да се наредат коцките на плочката. На пример, за N=7, коцките можат да се наредат на следните 17 начини:
Влез
Во првиот и единствен ред е запишан еден цел број N (3 <= N <= 80), кои ја означува должината на плочката.
Во тест случаи кои вредат најмалку 50% од поените, N ќе биде број помал или еднаков на 20 (3 <= N <= 20).
Излез
Излезот се состои од еден ред во кој треба да го отпечатите бројот на различни начини на кои може да се наредат коцките на плочката.
Забелешка: Резултатот може да е мнооогу голем број - користите тип на податок кој поддржува чување на 64-битни цели броеви, како int64 и qword во Pascal, или long long во C/C++.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 3 | излез 2 |
влез 7 | излез 17 |
влез 10 | излез 72 |
Објаснување за првиот пример: Двата начини се '@@@' и 'XXX'. Притоа, '@' означува празно подножје, додека 'X' означува подножје на кое има поставено коцка.
Објаснување за третиот пример: Фигурите не мора да се секвенци со иста должина и може да се одделени со повеќе од едно празно подножје. На пример, следново пополнување е валидно и треба да се брои: 'XXX@@XXXXX' (една секвенца од три коцки и една секвенца од пет коцки).