시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 18 10 7 46.667%

문제

You are given an array of n integers, a1, a2, . . . , an. Each integer is between 0 and 2k − 1, inclusive.

Let’s say that f(x) is the smallest i, such that (ai&x) ≠ ai, or 0, if there are no such i. (a&b) is the bitwise AND operation.

Find f(0) + f(1) + . . . + f(2k − 1). As this value may be very large, find it modulo 998 244 353.

입력

The first line contains two integers: n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 60).

The next line contains n integers: a1, a2, . . . , an (0 ≤ ai < 2k).

출력

Print one integer: f(0) + f(1) + . . . + f(2k − 1), modulo 998 244 353.

예제 입력 1

2 1
0 1

예제 출력 1

2

예제 입력 2

2 2
2 1

예제 출력 2

4

예제 입력 3

5 10
389 144 883 761 556

예제 출력 3

1118

힌트

In the first example, f(0) = 2, f(1) = 0.

In the second example, f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 0.

출처

Camp > Petrozavodsk Programming Camp > Winter 2020 > Day 3 I번

  • 문제를 만든 사람: 300iq