题目描述

有 $N$ 个小朋友坐成一排，他们的位置编号为 $1, 2, \dots, N$，年龄分别为 $A_1, A_2, \dots, A_n$。

请你编程解决以下两个问题：

1. 从这 $N$ 个小朋友中挑选出任意 $K$（$1 \leq K \leq N$）个小朋友，将他们的年龄进行按位或运算，能得到的最大值 $\text{Max}$ 是多少？
2. 有多少种不同的挑选方案，使得挑选出的小朋友的年龄按位或运算结果等于 $\text{Max}$？（注：若两个方案挑选的小朋友位置不同，则视为不同方案）

输入格式

• 第 1 行输入整数 $N$，代表小朋友的总数。
• 第 2 行输入 $N$ 个整数，代表每个小朋友的年龄 $A_1, A_2, \dots, A_n$。

输出格式

• 第 1 行输出最大值 $\text{Max}$。
• 第 2 行输出满足条件的方案数。

样例

样例输入 1

3
5 1 1

样例输出 1

5
4

样例解释 1

最大值为 5，对应的方案有：

• 仅选择第 1 个小朋友（年龄 5）。
• 选择第 1 个和第 2 个小朋友（$5 | 1 = 5$）。
• 选择第 1 个和第 3 个小朋友（$5 | 1 = 5$）。
• 选择所有 3 个小朋友（$5 | 1 | 1 = 5$）。 共 4 种方案。

样例输入 2

4
10 10 10 10

样例输出 2

10
15

样例输入 3

5
3 1 2 4 5

样例输出 3

7
17

数据范围

对于 $100\%$ 的数据，$1 \leq N \leq 18$，$1 \leq A_i \leq 10^5$。

说明

• 按位或运算（$|$）是双目运算符，其运算规则为：两个二进制数的对应位中，只要有一个为 1，则该位结果为 1，否则为 0。
• 子集的定义：从 $N$ 个元素中选择至少 1 个元素组成的集合，不同位置的元素即使值相同也视为不同元素。