Zenyk 有 $n$ 个球，球上分别写有整数 $a_1, \dots, a_n$，此外还有 $k$ 个盒子。你需要将每个球放入一个盒子中，且每个盒子必须至少包含一个球。一个盒子的价值定义为该盒子中所有球上整数的按位与（bitwise AND）结果。

请找出所有盒子价值之和（常规加法）的最大值，以及实现该最大和的方案数。注意，盒子中球的顺序不重要。然而，所有盒子都是不同的，且所有球也都是不同的，即使某些球上的整数相同。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 10^5$)。下一行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_j \le 10^9$)。

输出格式

输出两个整数。第一个整数为所有盒子价值之和的最大值。第二个整数为实现该最大和的方案数，对 $10^9 + 7$ 取模。

样例

输入格式 1

3 2
4 7 5

输出格式 1

11 2

输入格式 2

4 1
44 47 74 77

输出格式 2

8 1

输入格式 3

4 4
44 47 74 77

输出格式 3

242 24