<prompt> Unapewa nambari tatu n, m na k. Zingatia algoriti ifuatayo ili kupata kipengee cha juu zaidi cha safu kamili ya nambari chanya:Unapaswa kuunda safu ya safu ambayo ina sifa zifuatazo: arr ina nambari kamili n. 1 arri m ambapo 0 i n. Baada ya kutumia algoriti iliyotajwa kwa arr, thamani search_cost ni sawa na k.Rejesha _idadi ya njia_ za kuunda safu arr chini ya masharti yaliyotajwa. Kadiri jibu linavyoweza kuwa kubwa, jibu lazima likokotolewa modulo 109 7.Mfano wa 1:Ingizo: n 2, m 3, k 1Pato: 6Maelezo: Safu zinazowezekana ni 1, 1, 2, 1, 2, 2, 3, 1, 3, 2 3, 3Mfano wa 2:Ingizo: n 5, m 2, k 3Pato: 0Maelezo: Hakuna safu zinazowezekana zinazokidhi masharti yaliyotajwa.Mfano wa 3:Ingizo: n 9, m 1, k 1Pato: 1Maelezo: Safu inayowezekana pekee ni 1, 1, 1, 1, 1, 1, 1, 1, 1Vikwazo: 1 n 50 1 m 100 0 k n  <response>: def waysToBuildArrayn, m, k: mod 109 7 dp 0 k1 kwa _ katika safun1 dp00 1 kwa i katika masafa1, n1: kwa j katika safuk1: kwa x katika safu1, m1: ikiwa j 