Circle of Friends

Time limit7sMemory limit1024 MB

Summary

Count the ways to cut a circle of n cards into contiguous arcs so that each arc's bitwise AND is nonzero, modulo 998244353.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Prefix sum
Solved: No attempts yet

Problem

There is a group of friends sitting in a circle. Each friend is holding a card containing a positive integer. You would like to split the circle of friends into one or more groups. Each group must be a contiguous subsection of the circle. In addition, for each group, the bitwise AND of all values on the cards of the members of the group, taken together, must be nonzero. Count the number of ways you could split the circle of friends into groups.

Input

The first line of input contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ), which is the number of friends in the circle. Each of the next $n$ lines contains a single integer $a$ ( $1 \le a < 2^{60}$ ). These are the positive integers on the cards held by the friends, in the order that the friends are sitting. The last friend in the list is sitting next to the first friend in the list.

Output

Output a single integer, which is the number of ways to split the circle of friends into groups. Since this number may be very large, output it modulo 998,244,353.

Examples1

Example 1
Input
```
4
14
13
11
7
```
Expected output
```
11
```