Decorated Subset Partition

You are given a sequence of positive integers of length n (not necessarily distinct). For any set A with distinct elements extracted from some segment of the sequence, define its decorated subset as follows:

[ f(A)={ a\in A \mid \forall, b\in A\setminus{a},; a,|,b\neq b }]

Here the symbol | denotes the bitwise OR operation, and \(b\in A\setminus\{a\}\) means \(b\in A\) and \(b\neq a\).

Miku has a sequence of n positive integers \(a_i\). You are to partition the sequence consecutively into one or more contiguous segments. For each segment, let \(A_i\) be the set (i.e. the distinct elements) of numbers in that segment, and let \(f(A_i)\) be its decorated subset as defined above. The partition is called valid if all segments have the same decorated subset.

Your task is to count the number of valid ways to partition the sequence. Since the answer may be huge, output it modulo \(10^9+7\).

Note: A partition is defined by choosing boundaries between adjacent elements. For example, a partition into one segment is always allowed.

inputFormat

The first line contains a single integer n (the length of the sequence).

The second line contains n space‐separated positive integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer: the number of valid partitions modulo \(10^9+7\).

sample

3
1 2 3

1