任意k阶特殊三角矩阵的任意次幂求解咨询

我现在遇到一个矩阵幂运算的问题，想请教各位的思路。问题具体如下：

给定一个$k\times k$的矩阵$A_k$（其中$k\ge2$），矩阵形式为：

$$
A_{k}=
\begin{pmatrix}
1 & 1 & \cdots & 1 & 1 & 1 \
1 & 1 & \cdots & 1 &1 & 0\
&\vdots & &\vdots \
1 & 1 & \cdots & 0 & 0 & 0\
1 & 0 & \cdots & 0 & 0 & 0
\end{pmatrix}
$$

我需要计算这个矩阵的任意次幂$A_k^n$，但目前还没找到合适的方法推进。

我之前只了解对角化的思路——也就是通过求特征向量将矩阵转化为对角形式来计算幂，但这里$k$是任意值，而且只要$k\ge3$，特征值的计算就变得极其复杂，感觉这个方法不太适用。

如果各位有可行的思路或方法，麻烦分享一下，我会非常感激！另外，就算是针对$n$较大的情况（比如$n>5$），能给出计算$A_k^n$的具体思路也会很有帮助。

非常感谢大家！

备注：内容来源于stack exchange，提问作者Apple