Предизборна програма
Претстојат избори. И изборна кампања.
Нека постојат N телевизиски станици. Според изборниот законик, одредена партија може да откупи време на најмногу X од N-те телевизиски станици за позитивна кампања, како и на најмногу Y од N-те телевизиски станици за негативна (црна) кампања насочена против другите партии. Законикот дозволува откупување на време за двојна кампања (и позитивна и негативна) на најмногу K од N-те телевизиски станици.
Партијата "Пропаднати програмери" сака да ја презентира својата предизборна програма на телевизија. На колку различни начини таа може да го направи тоа? За два начини на презентирање велиме дека се различни доколку постои телевизиска станица на која во едниот начин се емитува еден тип на програма (позитивна, негативна или двојна), а во другиот начин се емитува друг тип на програма (или пак, во едниот начин на телевизијата не се емитува никаква програма, а во другиот начин се емитува).
Влез
Во првата линија е запишан еден цел број N (1 <= N <= 20), кој го означува бројот на телевизиски станици. Во втората линија се запишани два цели броја X и Y (0 <= X, Y <= N), кои го означуваат максималниот број на телевизиски станици на кои партијата може да откупи време за позитивна, односно за негативна кампања.
Во третата линија е запишан еден цел број K (0 <= K <= N), кој го означува бројот на станици на кои партијата смее да емитува двојна кампања.
Прва забелешка: Во тест случаи кои вредат најмалку 35% од поените, N ќе биде цел број помал или еднаков на 8 (1 <= N <= 8).
Втора забелешка: Резултатот може да биде прилично голем број, па потребно е да користите тип на податок кој поддржува чување на 64-битни цели броеви, како int64 и qword во Pascal, или long long во C/C++.
Излез
Отпечатете го бараниот број на начини.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 1 0 0 1 | излез 1 |
влез 2 1 1 2 | излез 9 |
влез 3 2 1 1 | излез 28 |
Објаснување за првиот пример: [ (/, /) ], каде / означува телевизиска станица на која партијата нема да откупи простор.
Објаснување за вториот пример: [ (/, /), (П, /), (Н, /), (/, П), (/, Н), (П, Н), (Н, П), (ПН, /), (/, ПН) ], каде / означува телевизиска станица на која партијата нема да откупи простор, П означува емитување на позитивна кампања, додека Н означува емитување на негативна кампања. ПН означува емитување на двојна кампања. Предизборно рекламирање од типот (П, ПН), на пример, би претставувало прекршување на изборниот законик, бидејќи тогаш партијата би емитувала позитивна кампања на 2 телевизиски станици, иако и е дозволено нејзино емитување на најмногу 1 станица (X=1).