题目描述

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

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

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

输入格式

第一行输入一个整数 $N$，代表小朋友的总数。

第二行输入 $N$ 个整数，代表每个小朋友的年龄 $A_1, A_2, \dots, A_N$。

输出格式

第一行输出最大值 $\text{Max}$。

第二行输出满足条件的方案数。

样例 #1

3
5 1 1

5
4

样例 #2

4
10 10 10 10

10
15

样例 #3

5
3 1 2 4 5

7
17

样例解释

样例 #1 解释

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

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

共 $4$ 种方案。

数据范围

• $1 \le N \le 18$
• $1 \le A_i \le 10^5$

提示

按位或运算（$|$）是双目运算符，其运算规则为：两个二进制数的对应位中，只要有一个为 $1$，则该位结果为 $1$，否则为 $0$。