Problem Description

Given an expression \( S \) consisting of the operation "exponentiation" on non-negative integers represented in Kanji characters, output the value of \( S \) modulo one billion nine in Kanji characters.

Non-negative integers are represented in standard Japanese Kanji notation. Note the following points:

• The characters used in this problem are 〇, 一, 二, 三, 四, 五, 六, 七, 八, 九, 十, 百, 千, 万, 億.
• \( 0 \) is represented as "〇". The character 〇 is not used for positive integers.
• \( 10^3 \) is represented as "千" (not "一千"). Similarly, \( 10^7 \) is "千万", and \( 10^{11} \) is "千億".
• \( 10^4 \) is represented as "一万" (not "万"). Similarly, \( 10^8 \) is "一億".

Also, it is agreed that "〇の〇乗" (zero to the power of zero) is one.

Input Format

\( S \)

The input is encoded in UTF-8 (without BOM). The character 六 is U+516D (not the compatibility character U+F9D1).

Output Format

Output the result of the expression \( S \) modulo one billion nine in Kanji characters. The output should be encoded in UTF-8 (without BOM). The character 六 should be U+516D.

Sample Input and Output

Sample Input #1

四の三の二乗乗

Sample Output #1

二十六万二千百四十四

Sample Input #2

四の三乗の二乗

Sample Output #2

四千九十六

Sample Input #3

十億十

Sample Output #3

一

Sample Input #4

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

Sample Output #4

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

Notes/Hints

Constraints

• The number of characters in \( S \) is between one and one hundred thousand.
• Each character in \( S \) is one of 〇, 一, 二, 三, 四, 五, 六, 七, 八, 九, 十, 百, 千, 万, 億, の, 乗.
• \( S \) is a valid expression according to the problem specification.

Partial Points

• If you solve the dataset where the number of characters in \( S \) is at most one thousand, you will be awarded twenty points.
• If you solve the dataset without additional constraints, you will be awarded an additional eighty points.

Sample Explanation 4

Sample input/output files can be downloaded here.

见题面 Input 部分

见题面 Output 部分