SP25977 GSMATRIX - Matrix

邓克莱克先生收到朋友甘尼什先生赠送的一个大型矩阵 $A$，并被要求计算 $A^N$ 的结果。由于矩阵过大且时间紧迫，他希望能减少计算 $A^N$ 所需的矩阵乘法次数。请注意，邓克莱克先生会保存他已经计算过的所有矩阵，以便需要时能直接使用，而不必重新计算。 你需要帮助邓克莱克先生找出计算 $A^N$ 时所需的最少乘法次数。

第一行输入一个整数 $N$，表示矩阵的指数，满足 $0< N \leq 120$。

输出计算 $A^N$ 所需的最小乘法次数。 **本翻译由 AI 自动生成**