你知道807是誰嗎？不清楚也沒關係，小海知道。807是建國中學電子計算機研習社的學術長，更是225的數資班大電神，發明出了O(1)的迴文判斷演算法，七科奧林匹亞國手，更是獨立解決了資訊學上著名的P/NP問題。有一天，807終於想起來他身為一個高中生，學術能力是相當重要的，他在X上面發了一篇文：「今天遇到的問題是：

建電面試 - 學術專用題 pG

你會比較想教難一點的東西還是入門一點的東西，為什麼？那如果今天你的對幹或是其他學術跟你說他覺得這個別人會聽不懂，你會怎麼辦？

我回答：

我先會資訊，再會數學，最後大勝你；這題真的只是一個裸題，只要有更動時輸出Hash值就好。你還違背了專案開發時不用萬用標頭檔以致於編譯時間過長的原則，你不在乎，你只在乎七面奧林匹亞金牌要拌42號高嶺土。

接著我就考上學術長了，單靠我的機智和第七代反原子槍。我領先了小海三個平行宇宙。」笨如小海，當然不知道他在講什麼，他只知道 :place_of_worship:

有天，哀季希希和建北電資發生了第 7122 次紛爭，身為拆國低中茲訓社的學術長小海，因為807幫他扛住專題壓力，希望能調解這場紛爭。807開出了條件：如果能夠幫我處理文書，我就協助停止這場紛爭。原來，807雖然打字很快，但這種東西太浪費他研究專題的時間了，於是他叫小海設計一套文書軟體，支援插入和刪除字元，並輸出每個更改後的版本。但是要處理的文書量太大了，如果每次都把整篇文章印出來非常麻煩，因此807採用了折衷方案：輸出文章的 Hash 值，反正他不用 1 秒就能在腦中搜尋出合理的文章內容了。但一樣，笨如小海，他怎麼可能知道怎麼解決，因此他不得不將這道問題丟給了同樣身為建國中學電子計算機研習社大電神的你。

給定一個字串 $S$ ，有 $Q$ 次操作，每次操作符合下列其中一項：

1. 在指定位置插入字元
2. 刪除指定位置的字元
3. 輸出目前字串的Hash值，Hash值的計算方式是：$S_n + 27S_{n-1} + 27^2S_{n-2}...27^{n-1}S_1 = \sum_{i=0}^{n-1} 27^i S_{n-i} $，其中 $n$ 是字串長度，$S_i$ 是字串中的字元，a~z 分別代表 1 ~ 26

保證出現的字元存在於 a~z 由於Hash值可能會很大，請將輸出模 $10^9+7$ $n,\ Q\leq 5\times 10^5$