猴子島上有個傳統，猴王專向其他猴子從採收 的香蕉中抽成 ，但自己不採香蕉。

島上除猴王外有 20 隻猴子，每隻猴子每天固 定採收 80 根香蕉。 第 1 天猴王向 20 隻猴子各收 1 根香蕉，第 2 天也向 20 隻猴子各收 1 根香蕉，第 3 天之後 每天各收先前兩天所抽香蕉數的總和 (即：第 3 天，各收 2 根(1+1)；第 4 天，各收 3 根 (1+2)；第 5 天，各收 5 根(2+3)，… 依此類推)。

然而，猴王抽成來的香蕉不新鮮，隔天有一半 (或近一半), 即 香蕉數×0.5 註 1會壞掉。例如： 第 4 天時，前 3 天猴王抽成來的 55 根香蕉，會壞掉 27 根，剩 28 根， 第 4 天，新收 60 根， 第 4 天結束時，猴王有 88 根香蕉。 其他猴子擁有的香蕉比較新鮮，所以不會壞掉。

日子如此這般，當某天猴王收走其他猴子們所有的香蕉後，猴子們立即會發生暴動並選出 新猴王。此時，舊猴王必須發給新猴王以外的每一個猴子(包括自己共 20 隻)各 \( N \) 根香蕉, 剩餘的香蕉則由新猴王擁有。而 \( N \) 符合這樣條件:

• \( N \times 20 \leq \) \( 舊猴王原擁有總數 \times 95\% \)
• \( (N+1) \times 20 > 舊猴王原擁有總數 \times 95\% \)
• \( N \) 為正整數

例如：第 14 天原猴王有 10912 根香蕉，其他猴子各有 134 根香蕉，第 15 天每隻猴子又 採了 80 根香蕉變成 214 根，但猴王依照算法當天要收 610 根，全部香蕉給猴王之後，都 還不夠，所以引發暴動並產生新猴王。如前述之方式重分配後，新猴王拿到 496 根香蕉， 其他猴子(包括舊猴王) 則留下 462 根香蕉，然後下一天新猴王又向大家收 1 根香蕉，再一 天 1 根香蕉，再來 2 根香蕉，依此類推。 島上資源有限，所以總猴子數為固定 21 隻。

註 1： 向下取整

輸入格式

一個正整數 \(t\)，表示第 \(t\) 天，因為猴子一百萬年前就有，\( 1 \leq t \leq 100000000\)

輸出格式

輸出猴子(非猴王)第t天擁有的香蕉數量。

範例輸入1

2

範例輸出1

158

範例輸入2

28

範例輸出2

893

範例輸入3

65

範例輸出3

893

範例輸入4

15

範例輸出4

462