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

0 Judge

Code: 0


那樣的事,我絕不容許

在最後一刻,已經沒有人阻止的了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$之間,有幾種攻擊方法可以使他們突破結界?在一旁觀望的你能幫忙計算嗎?

sprout

而此時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
=><

範例輸出

14

公告

  • $2 \leq N \leq 1000$
  • 2016/12/26 07:51 放寬記憶體限制rejudge

Judge Setting

run-time limit: 20 ms
memory limit: 1213104 byte
測資數量: 0