普及-⏱ 1000ms💾 256MB#P3092

题目描述

从边长为 $3^k$ 的实心正方形开始:每一步把每个现存正方形九等分,挖去正中心的那一小块;余下的 $8$ 个小方块各自继续同样的操作,共进行 $k$ 步。求最终剩余面积与原面积之比,以最简分数 $a/b$ 输出。(比值为 $(8/9)^k$,用 128 位整数计算。)

输入格式

一行一个整数 $k$

输出格式

一行两个整数 a 和 b(空格分隔),表示比值的最简分数。

数据范围

$$0 \le k \le 40$$

样例输入 #1
0
样例输出 #1
1 1
样例输入 #2
1
样例输出 #2
8 9