<prompt> Kuna jaribio ambalo lina aina n za maswali. Umepewa lengwa kamili na safu kamili ya 0 ya 2D aina ambapo ainai counti, marksi inaonyesha kuwa kuna maswali counti ya aina ya ith. , na kila moja yao ina thamani ya alama marksi.Rejesha _idadi ya njia unazoweza kupata haswa_ lengwa _pointi katika mtihani_. Kwa kuwa jibu linaweza kuwa kubwa sana, lirudishe modulo 109 7.Kumbuka kwamba maswali ya aina moja hayawezi kutofautishwa. Kwa mfano, ikiwa kuna maswali 3 ya aina moja, basi kusuluhisha maswali ya 1 na 2 ni sawa na kusuluhisha maswali ya 1 na 3, au 2 na 3. maswali.Mfano wa 1:Ingizo: lengwa 6, aina 6,1,3,2,2,3Pato: 7Maelezo: Unaweza kupata pointi 6 katika mojawapo ya njia saba:- Tatua maswali 6 ya aina ya 0: 1 1 1 1 1 1 6- Tatua maswali 4 ya aina ya 0 na swali 1 la aina ya 1: 1 1 1 1 2 6- Tatua maswali 2 ya aina ya 0 na maswali 2 ya aina ya 1: 1 1 2 2 6- Tatua maswali 3 ya aina ya 0 na swali 1 la aina ya 2: 1 1 1 3 6- Tatua swali 1 la aina ya 0, swali 1 la aina ya 1 na swali 1 la aina ya 2: 1 2 3 6- Tatua maswali 3 ya aina ya 1: 2 2 2 6- Tatua maswali 2 ya aina ya 2: 3 3 6Mfano wa 2:Ingizo: lengwa 5, aina 50,1,50,2,50,5Pato: 4Maelezo: Unaweza kupata pointi 5 katika mojawapo ya njia nne:- Tatua maswali 5 ya aina ya 0: 1 1 1 1 1 5- Tatua maswali 3 ya aina ya 0 na swali 1 la aina ya 1: 1 1 1 2 5- Tatua maswali 1 ya aina ya 0 na maswali 2 ya aina ya 1: 1 2 2 5- Tatua swali 1 la aina ya 2: 5Mfano wa 3:Ingizo: lengwa 18, aina 6,1,3,2,2,3Pato: 1Maelezo: Unaweza kupata pointi 18 pekee kwa kujibu maswali yote.Vikwazo: 1 lengo 1000 n aina.urefu 1 n 50 ainai.urefu 2 1 counti, marksi 50  <response>: def numberOfWayslengo, aina: MOD 109 7 dp 0 lengo 1 dp0 1 kwa kuhesabu, alama katika aina: dptmp 0 lengo 1 kwa mimi katika anuwai lengo 1: kwa j katika safu hesabu 1: ikiwa j alama i lengo: dptmpi j alama dptmpi j alama dpi MOD dp dptmp rudisha dplengo 