國際象棋中的騎士可以按下圖所示進(jìn)行移動(dòng)：

?.? ? ? ? ? ?

這一次，我們將?“騎士” 放在電話撥號盤的任意數(shù)字鍵（如上圖所示）上，接下來，騎士將會(huì)跳?N-1 步。每一步必須是從一個(gè)數(shù)字鍵跳到另一個(gè)數(shù)字鍵。

每當(dāng)它落在一個(gè)鍵上（包括騎士的初始位置），都會(huì)撥出鍵所對應(yīng)的數(shù)字，總共按下?N 位數(shù)字。

你能用這種方式撥出多少個(gè)不同的號碼？

因?yàn)榇鸢缚赡芎艽?#xff0c;所以輸出答案模?10^9 + 7。

?

示例 1：

輸入：1 輸出：10

示例 2：

輸入：2 輸出：20

示例 3：

輸入：3 輸出：46

?

提示：

• 1 <= N <= 5000

總結(jié)

以上是生活随笔為你收集整理的935. 骑士拨号器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。