那樣的事，我絕不容許

在最後一刻，已經沒有人阻止的了Sayaka Miki的墮落，陷入瘋狂的她最終被自己的靈魂給吞噬，化為魔女。一個想解救眾人免於魔女的侵害的善意，卻反而落得成為魔女的下場，這就是魔法少女的宿命。不過這也是為了這個宇宙運作的著想，唯有少女從希望化為絕望的過程中釋放的能量才能推動宇宙的運作。$Kyubey$的解釋聽起來刺耳且邪惡。

「沒有方法可以救回Sayaka Miki了嗎？」見證這慘劇的Kyoko Sakura向$Kyubey$詢問，這危險的生物是他們唯一的希望，但是只得到簡短的回覆：「不知道。」如果沒有方法的話，我們就來開創一個吧。Kyoko Sakura心中盤算著，隔天她偷偷的找了Madoka Kaname，希望能用她最要好朋友的聲音喚回Sayaka Miki，抱著決心的兩人就往昨日的事故地點前進了。當他們到達目的地時卻發現Sayaka Miki化為的魔女結界十分難以突破！需要使用與該結界相同的震盪模式才有機會打破這個結界的入口，機智的Kyoko Sakura立刻找出了震盪模式，並以字串$S$表示，震盪模式由$<$、$=$、$>$來表示，表示本次攻擊結界需要的攻擊力量大小與上一次的關係是什麼，比如說震盪模式$<=>$接受攻擊大小依序是$1,5,5,2$，但不接受$1,6,5,1$，已知Kyoko Sakura的攻擊力落在$1\sim N$之間，有幾種攻擊方法可以使他們突破結界？在一旁觀望的你能幫忙計算嗎？

而此時Homura Akemi感受到了Kyoko Sakura與Madoka Kaname似乎又在做傻事，趕緊前去，只見負重傷搖搖晃晃的Kyoko Sakura與不知為何的暈過去的Madoka Kaname，Homura Akemi把她抱了起來，此時Kyoko Sakura笑了一下，放出了結界把她自己與魔女關在一起。「早知道一開始就該這麼做，」Kyoko Sakura說著「那孩子就給你照顧了。」轉瞬間，結界已被前所未見的爆炸所壟罩，一切消失於虛無之中。

輸入說明

只有一筆測資，測資的第一行有一個數字$N$，表示$Kyoko Sakura$的攻擊力範圍為$1\sim N$，下一行有一個長度是$N-1$的震盪模式序列，保證一定是合法的序列。

輸出說明

輸出$Kyoko Sakura$有幾種可被震盪模式接受的攻擊順序，並換行。由於答案可能非常的大，請輸出其除以$1000000009$的餘數就好。

範例輸入

4
=><

59. 那樣的事，我絕不容許

那樣的事，我絕不容許

輸入說明

輸出說明

範例輸入

範例輸出

公告

Judge Setting