<prompt> Una vifurushi n ambavyo unajaribu kuweka kwenye visanduku, kifurushi kimoja katika kila kisanduku. Kuna wasambazaji m ambao kila mmoja hutoa masanduku ya saizi tofauti yenye usambazaji usio na kikomo. Kifurushi kinaweza kuwekwa kwenye kisanduku ikiwa saizi ya kifurushi ni chini ya au sawa na saizi ya kisanduku.Ukubwa wa kifurushi hutolewa kama safu kamili furushi, ambapo furushii ni ukubwa wa kifurushi cha ith. Wasambazaji wametolewa kama safu kamili ya 2D masanduku, ambapo masandukuj ni safu ya sanduku za ukubwa ambazo msambazaji jth hutoa.Unataka kuchagua mtoa huduma mmoja na utumie visanduku kutoka kwao ili kwamba jumla ya nafasi iliyopotea ipunguzwe. Kwa kila kifurushi kwenye kisanduku, tunafafanua nafasi iliyopotea kuwa ukubwa wa kisanduku - ukubwa wa kifurushi. Jumla ya nafasi iliyopotea ni jumla ya nafasi iliyopotea katika masanduku yote. Kwa mfano, ikiwa itabidi utoshee vifurushi vyenye ukubwa 2,3,5 na msambazaji atoe visanduku vya ukubwa 4,8, unaweza kutoshea vifurushi vya ukubwa-2 na saizi- 3 ndani ya visanduku viwili vya ukubwa-4 na kifurushi chenye ukubwa-5 kwenye kisanduku cha ukubwa-8. Hii ingesababisha upotevu wa 4-2 4-3 8-5 6.Rejesha kiwango cha chini cha nafasi iliyopotea kwa kuchagua msambazaji kisanduku kabisa, au_ -1 _ikiwa haiwezekani kutoshea vifurushi vyote ndani ya visanduku._ Kwa kuwa jibu linaweza kuwa kubwa, irudishe modulo 109 7.Mfano wa 1:Ingizo: vifurushi 2,3,5, visanduku 4,8,2,8Pato: 6Maelezo: Ni bora kuchagua msambazaji wa kwanza, kwa kutumia visanduku viwili vya ukubwa-4 na sanduku moja la saizi-8.Jumla ya taka ni 4-2 4-3 8-5 6.Mfano wa 2:Ingizo: vifurushi 2,3,5, visanduku 1,4,2,3,3,4Pato: -1Maelezo: Hakuna kisanduku ambacho kifurushi cha ukubwa wa 5 kinaweza kutoshea.Mfano wa 3:Ingizo: vifurushi 3,5,8,10,11,12, visanduku 12,11,9,10,5,14 Pato: 9Maelezo: Ni vyema kuchagua msambazaji wa tatu, kwa kutumia visanduku viwili vya ukubwa-5, visanduku viwili vya saizi-10, na visanduku viwili vya saizi-14.Jumla ya taka ni 5-3 5-5 10-8 10-10 14-11 14-12 9.Vikwazo: n packages.length m masanduku.urefu 1 n 105 1 m 105 1 vifurushii 105 1 masandukuj.urefu 105 1 masandukujk 105 jumlasandukuj.urefu 105 Vipengele katika kisandukuj ni tofauti.  <response>: def check_powers_of_threen: int - bool: wakati n 0: ikiwa n 3 2: kurudi Uongo n 3 kurudi Kweli 