给定一个整数序列 $$$1, 2, \dots, n$$$。您必须将其分为两个集合 $$$A$$$ 和 $$$B$$$,使得每个元素恰好属于一个集合,并且 $$$|sum(A) - sum(B)|$$$ 是最小可能的。
值 $$$|x|$$$ 是 $$$x$$$ 的绝对值,$$$sum(S)$$$ 是集合 $$$S$$$ 的元素之和。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^9$$$)。
输出
打印一个整数 — 如果将初始序列 $$$1, 2, \dots, n$$$ 分为两组 $$$A$$$ 和 $$$B$$$,则 $$$|sum(A) - sum(B)|$$$ 的最小可能值。
示例
输入 #1
3
输出 #1
0
输入 #2
5
输出 #2
1
输入 #3
6
输出 #3
1
注意
示例的一些(不是全部)可能答案:
在第一个示例中,您可以将初始序列分为集合 $$$A = \{1, 2\}$$$ 和 $$$B = \{3\}$$$,因此答案是 $$$0$$$。
在第二个示例中,您可以将初始序列分为集合 $$$A = \{1, 3, 4\}$$$ 和 $$$B = \{2, 5\}$$$,因此答案是 $$$1$$$。
在第三个示例中,您可以将初始序列分为集合 $$$A = \{1, 4, 5\}$$$ 和 $$$B = \{2, 3, 6\}$$$,因此答案是 $$$1$$$。