J - Japanese Exponentation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100

うさぎは,4^{3^2} は「四の三の二乗乗」であり,(4^3)^2 は「四の三乗の二乗」である,というように,日本語は括弧を使わずに,しかも簡潔に冪乗の計算順を表せることに気づいた.こんな便利な言語を使わない手はないので,日本語で計算できるようになろう.

問題文

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

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

  • 本問で用いられる文字は , , , , , , , , , , , , , , である.
  • 0 は「〇」である.正の整数には文字 は用いない.
  • 10^3 は「千」である (「一千」ではない).同様に,10^7 は「千万」,10^{11} は「千億」である.
  • 10^4 は「一万」である (「万」ではない).同様に,10^8 は「一億」である.

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

制約

  • S に含まれる文字の個数は一以上十万以下である.
  • S の各文字は , , , , , , , , , , , , , , , , のいずれかである.
  • S は問題文の仕様を満たす正しい式である.

部分点

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

入力

S

入力の文字コードは UTF-8 (BOM なし) である. は U+516D である (互換文字の U+F9D1 ではない).

出力

S の計算結果を十億九で割った余りを漢数字で出力せよ.出力の文字コードは UTF-8 (BOM なし) であること. は U+516D であること.


入力例 1

四の三の二乗乗

出力例 1

二十六万二千百四十四

入力例 2

四の三乗の二乗

出力例 2

四千九十六

入力例 3

十億十

出力例 3


入力例 4

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

出力例 4

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

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