問題文

漢数字で表される非負整数に対する，演算「a の b 乗」のみからなる式 S が与えられるので，その値を十億九で割った余りを漢数字で出力せよ．

非負整数は漢数字によって，標準的な日本語で表記する．以下の点に注意せよ．

• 本問で用いられる文字は 〇, 一, 二, 三, 四, 五, 六, 七, 八, 九, 十, 百, 千, 万, 億 である．
• 0 は「〇」である．正の整数には文字 〇 は用いない．
• 10^3 は「千」である (「一千」ではない)．同様に，10^7 は「千万」，10^{11} は「千億」である．
• 10^4 は「一万」である (「万」ではない)．同様に，10^8 は「一億」である．

また，「〇の〇乗」は一であると約束する．

制約

• S に含まれる文字の個数は一以上十万以下である．
• S の各文字は 〇, 一, 二, 三, 四, 五, 六, 七, 八, 九, 十, 百, 千, 万, 億, の, 乗 のいずれかである．
• S は問題文の仕様を満たす正しい式である．

部分点

• S に含まれる文字の個数が千以下であるデータセットに正解した場合は，二十点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に八十点が与えられる．

入力例 1

四の三の二乗乗

出力例 1

二十六万二千百四十四

入力例 2

四の三乗の二乗

出力例 2

四千九十六

入力例 3

十億十

出力例 3

一

入力例 4

一億二千三百四十五万六千七百八十九の二の〇の〇乗乗乗

出力例 4

六億千三百一万六千三百十九

サンプル入出力ファイルはこちらからダウンロードできる．