Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm số lượng giá trị xor khác nhau của các tập con.

Input

Dòng đầu tiên chứa một số nguyên \(n\): kích thước của mảng.

Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): các phần tử của mảng.

Output

In ra một số nguyên: số lượng giá trị xor khác nhau của các tập con.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(0 \le x_i \le 10^9\)

Example

3
3 6 5

4

Giải thích: Các giá trị sau có thể là xor của một tập con:

• \(0 = \text{xor of the empty set}\)

• \(3 = 3\)

• \(5 = 3 \oplus 6\)

• \(6 = 3 \oplus 5\)

Trong trường hợp này, không có giá trị nào khác có thể là xor của một tập con.