<prompt> Unapewa gridi kamili ya gridi ya m x n yenye faharasa na k kamili. Kwa sasa uko kwenye nafasi 0, 0 na unataka kufikia nafasi m - 1, n - 1 ukisogea tu chini au kulia.Rejesha _idadi ya njia ambapo jumla ya vipengele kwenye njia inaweza kugawanywa kwa_ k. Kwa kuwa jibu linaweza kuwa kubwa sana, lirudishe modulo 109 7.Mfano wa 1:Ingizo: gridi 5,2,4,3,0,5,0,7,2, k 3Pato: 2Maelezo: Kuna njia mbili ambapo jumla ya vipengele kwenye njia hiyo hugawanywa kwa k.Njia ya kwanza iliyoangaziwa kwa rangi nyekundu ina jumla ya 5 2 4 5 2 18 ambayo inaweza kugawanywa na 3.Njia ya pili iliyoangaziwa kwa bluu ina jumla ya 5 3 0 5 2 15 ambayo inaweza kugawanywa na 3.Mfano wa 2:Ingizo: gridi 0,0, k 5Pato: 1Maelezo: Njia iliyoangaziwa kwa rangi nyekundu ina jumla ya 0 0 0 ambayo inaweza kugawanywa na 5.Mfano wa 3:Ingizo: gridi 7,3,4,9,2,3,6,2,2,3,7,0, k 1Pato: 10Maelezo: Kila nambari kamili inaweza kugawanywa na 1 kwa hivyo jumla ya vipengee kwenye kila njia inayowezekana inaweza kugawanywa kwa k.Vikwazo: m grid.length n gridi ya taifai.length 1 m, n 5 104 1 m n 5 104 0 gridiij 100 1 k 50  <response>: def njiagridi, m, n, i, j, k, jumla, dp: ikiwa i m - 1 na j n - 1: rudisha 1 ikiwa jumla gridiij k 0 mwingine 0 ikiwa dpijsum -1: zaidi 0 ikiwa mimi 1 