Even more efficient last 'Fibonacci' digit in base d

This kata is a spinoff of Efficient last Fibonacci digit in base d, which is a spinoff of Find last Fibonacci digit [hardcore version], which is a spinoff of Find last Fibonacci digit.

Preface

The $nn$th Fibonacci number can be computed based on the recurrence $F_n=F_{n-1}+F_{n-2}F\_n=F\_\{n-1\}+F\_\{n-2\}$ (the first few numbers are $0,1,1,2,3,5,8,13,21,\mathrm{.}\mathrm{.}\mathrm{.}0,1,1,2,3,5,8,13,21,...$). Usually, we would have $F_0=0F\_0=0$ and $F_1=1F\_1=1$, or $F_0=1F\_0=1$ and $F_1=1F\_1=1$, but for this kata, you will be provided custom starting terms $xx$ and $yy$ for $F_{0}F\_0$ and $F_{1}F\_1$. Since this isn't really the Fibonacci sequence, let's call this sequence $U_{n}U\_n$. Based on this, this is what we have so far:

• $U_0=xU\_0=x$
• $U_1=yU\_1=y$
• $U_n=U_{n-1}+U_{n-2}U\_n=U\_\{n-1\}+U\_\{n-2\}$

Task

Given $xx$, $yy$, $nn$ and $kk$, find the last digit of $U_{n}U\_n$ in base $kk$ based on the above. In other words, find $U_n(\mathrm{m}\mathrm{o}\mathrm{d}k)U\_n\backslash pmod\; k$. Your function should return an integer.

Examples

If $x=5x=5$, $y=7y=7$, $n=3n=3$ and $k=10k=10$, we have the following:

This means that the last digit of $U_{3}U\_3$ in base $1010$ is $99$.

---

If $x=4x=4$, $y=9y=9$, $n=6n=6$ and $k=8k=8$, we have the following:

This means that the last digit of $U_{6}U\_6$ in base $88$ is $44$.

---

If $x=15x=15$, $y=15y=15$, $n=4n=4$ and $k=16k=16$, we have the following:

This means that the last digit of $U_{4}U\_4$ in base $1616$ is $bb$, or $1111$ in base $1010$.

Constraints

• $0\le n\le 2^{1234}0\backslash leq\; n\backslash leq\; 2^\{1234\}$
• $0\le k\le 2^{987}0\backslash leq\; k\backslash leq\; 2^\{987\}$
• $0\le x\le y\le 2^{876}0\backslash leq\; x\backslash leq\; y\backslash leq\; 2^\{876\}$

Hints (only use these if you need them)

• Hint 1

  Do you notice a pattern in the examples?
• Hint 2

  Look at the coefficients. Do you notice anything?
• Hint 3

  There must be a reason why I included the first few Fibonacci numbers in the preface.