$\def\bk{\color{#333333}}$九連環是一種源於中國的傳統智力遊戲，韓國稱為留客珠、留客環，這種古老玩具以往在民間極為普及。它包含著九個相同的圓環及一把「劍」，遊戲目標是把九個圓環全套上或卸下。不斷重複的盲目操作,即可以讓狀態在數學的數列結構中向左或向右移動至終點，且這也是唯一的方式。此性質和魔術方塊是很不同的。對於沒有受過近代數學分析訓練者可能會花上較多時間處理此問題，但一般皆稍受提點即可快速上手，此性質也是和魔術方塊很不同。 操作過程中若是移動方向錯誤，則會遇到端點狀態，使操作折返即可。經提點後的操作者剩下的智力活動空間剩下對於判斷半完成品的接續操作應該由什麼開始才能夠以最快的方式解決。 雖然在了解解決方法之後，九連環做為玩具的耐玩性會大幅下降，但就九連環背後的數學結構和實踐其數學結構的機械設計巧思，九連環仍是一個非常巧妙的發明。

(從左到右分別是 完整未解 解到一半 完全解出 的九連環)

以上參考自維基百科：https://zh.wikipedia.org/zh-tw/%E4%B9%9D%E9%80%A3%E7%92%B0

這天Chris突然被一股神祕中國民族五千年力量所控制

瘋狂的去玩這個偉大的中國歷史傳統發明 --- 九連環

在解這些神奇的環的時候也得到許多心得

也被他的二進位結構以及與葛雷碼的等同性深感沉迷

九連環的規則如下(以上面中間那張圖做說明):

我們可以把他畫成下方這張簡圖

預設將劍鋒朝向右側，圓環狀態分成 在劍上的$1$ 和 在劍下的$0$

最終的目標是利用最少的步數將這些環的狀態都變成$0$

我們由右往左將環編號為$1$到$\bk N$並訂$\bk{a_k}$為第$\bk k$環的狀態(這邊的$\bk N$為$9$)

只要我們符合:

$\bk{a_{k-1}=1}$且$\bk{a_{k-2} \sim a_1=0}$ 則 可以用$1$步改變$\bk{a_k(k \ge 3)}$的狀態

或是當$\bk{a_2=a_1}$時 則 可以用$1$步同時改變$\bk{a_2}$和$\bk{a_1}$的狀態

我們也可以隨時用$1$步操作$\bk{a_1}$的狀態

(改變狀態表示把環的狀態從$0$變為$1$或相反) 

就上面簡圖而言，可以把狀態寫成$010011000$，並且我們可以用$1$步做的操作有

把環$5$拿下來 或 把環$1$跟環$2$同時拿上去 或 把環$1$拿上去

今天Chris心血來潮解了一個$\bk N$連環，但解到一半睡著了

醒來面前就只剩下一個解到一半的$\bk N$連環(環的狀態有些$1$有些$0$)

他希望用最少步數從這個狀態解出來(將所有環狀態變為$0$)，但他睡太久忘記怎麼解了

所以需要聰明的你幫他算一下最少需要幾步才能把他解出來

由於答案可能很大，請輸出答案對$\bk{10^9+7}$取的模