<prompt> Unachora uzio wa machapisho n na k rangi tofauti. Lazima uchora machapisho kwa kufuata sheria hizi: Kila chapisho lazima liwekwe rangi moja kabisa.Hakuwezi kuwa na machapisho matatu au zaidi mfululizo yenye rangi sawa.Kwa kuzingatia nambari mbili kamili n na k, rudisha _idadi ya njia unazoweza kupaka uzio_.Mfano wa 1:Ingizo: n 3, k 2Pato: 6Maelezo: Uwezekano wote umeonyeshwa.Kumbuka kuwa kupaka machapisho yote mekundu au machapisho yote ya kijani ni batili kwa sababu hakuwezi kuwa na machapisho matatu mfululizo yenye rangi sawa.Mfano wa 2:Ingizo: n 1, k 1Pato: 1Mfano wa 3:Ingizo: n 7, k 2Pato: 42Vikwazo: 1 n 50 1 k 105 Testcases hutengenezwa hivi kwamba jibu liko katika safu 0, 231 - 1 kwa n na k zilizotolewa.  <response>: chatudef numNjian, k: ikiwa n 0: kurudi 0 ikiwa n 1: kurudi k sawa k tofauti k k - 1 kwa i katika safu2, n: temp tofauti tofauti sawa tofauti k - 1 sawa joto kurudi sawa tofautimaelezoTunaanza na visa viwili wakati n ni sawa na 0 au 1.Ikiwa n ni sawa na 0, inamaanisha hakuna machapisho, kwa hivyo matokeo yatakuwa 0.Ikiwa n ni sawa na 1, inamaanisha kuna chapisho moja tu na rangi k za kuchagua, kwa hivyo matokeo yatakuwa k.Baada ya hapo, tunaunda vigezo viwili: sawa na tofauti. sawa huhifadhi idadi ya njia za kuweka uzio rangi kwenye nafasi i, ili rangi ya posti ifanane na ile ya posti i-1. different huhifadhi idadi ya njia za kuweka rangi kwenye chapisho katika nafasi i, ili rangi ya chapisho i iwe tofauti na ile ya chapisho i-1.Kwa machapisho mawili ya kwanza, kuna k njia za kuzipaka rangi sawa, na kk-1 njia za kuzipaka rangi tofauti.Kisha tunatumia kitanzi kuanzia chapisho la tatu i2 hadi chapisho la mwisho in-1.Katika kila marudio, tunasasisha tofauti kwa kuongeza thamani sawa na tofauti za awali na kuzidisha kwa k-1. Hii ni kwa sababu kwa rangi tofauti, zinaweza kutoka kwa rangi sawa au rangi tofauti, kwa hivyo nyongeza. Na kisha tunaizidisha kwa k-1 ili kuzingatia mchanganyiko wote wa rangi unaowezekana ukiondoa rangi ya awali. Baada ya hapo, tunasasisha sawa kulingana na thamani tofauti iliyotangulia, kwa sababu sasa tunahitaji kuzingatia chapisho la sasa kuwa na rangi sawa na chapisho lililotangulia.Hatimaye, tunarejesha jumla ya idadi ya njia ambazo ni jumla ya sawa na tofauti. 