AT_xmascon18_j Japanese Exponentation

给定一个只包含“$ a $ 的 $ b $ 次方”运算的表达式 $ S $，其中 $ a $ 和 $ b $ 都用汉数字表示，求其值对 $ 10^9 + 9 $ 取余的结果，并用汉数字输出。 非负整数用标准日语汉数字表示。注意以下几点： - 本题使用的字符有：`〇`、`一`、`二`、`三`、`四`、`五`、`六`、`七`、`八`、`九`、`十`、`百`、`千`、`万`、`億`。 - $ 0 $ 表示为“〇”。正整数中不使用字符“〇”。 - $ 10^3 $ 表示为“千”（不是“一千”）。同理，$ 10^7 $ 表示为“千万”，$ 10^{11} $ 表示为“千億”。 - $ 10^4 $ 表示为“一万”（不是“万”）。同理，$ 10^8 $ 表示为“一億”。 另外，约定“〇の〇乗”为一。

> $ S $ 输入的字符编码为 UTF-8（无 BOM）。`六` 的 Unicode 编码为 U+516D（不是兼容字符 U+F9D1）。

将表达式 $ S $ 的计算结果对 $ 10^9 + 9 $ 取余后的结果用汉数字输出。输出的字符编码为 UTF-8（无 BOM），`六` 的 Unicode 编码为 U+516D。

## 约束 - $ S $ 中包含的字符数不少于 1 个且不超过 100000 个。 - $ S $ 的每个字符均为 `〇`、`一`、`二`、`三`、`四`、`五`、`六`、`七`、`八`、`九`、`十`、`百`、`千`、`万`、`億`、`の`、`乗` 之一。 - $ S $ 是符合题目描述的合法表达式。 ## 部分分 - 若 $ S $ 中字符数不超过 1000 的数据集答对，得 20 分。 - 若在无额外约束的数据集答对，另得 80 分。 ## 样例说明 4 样例输入输出文件可从[这里](https://img.atcoder.jp/xmascon18/japanese-sample.zip)下载。 由 ChatGPT 4.1 翻译