Problem D
Circle of Friends

There is a posse 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.


The first line of input contains a single integer $n$ ($1 \leq n \leq 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 circle, in the order that the friends are sitting. Note that since they’re in a circle, the last friend in the list is sitting next to the first friend in the list.


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$.

Sample Input 1 Sample Output 1
CPU Time limit 7 seconds
Memory limit 2048 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in