题目描述

Sanhai 最近在学习集合。

Sanhai 定义对于一个非空子集的各元素之和称为他的一个子集合。Sanhai 很喜欢一个 好的 集合 $S$，满足 $S$ 的任意两个子集和均不相等。可是 Sanhai 不想要很大的数字，于是 Sanhai 想找到一个元素和最小的长度为 $n$ 的 好的 集合。

输入格式

输入一个 $n$，($1 \le n \le 6 \times 10^6$)。

输出格式

输出最小的长度为 $n$ 的 好的 集合，但是即使 Sanhai 不想要很大的数字，但是数字还是会很大，输出其所有数模 $10^9 + 114514$ 的结果

样例

2

1 2