GitHub 源文件 Markdown 中文

Counting Paired DNA Strands

Estimated time limit: 0.5 seconds. Memory limit: 128 MB.

The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of \(0.5\) seconds. See the benchmark environment.

Story

In this model of double-stranded, non-circular DNA, the two strands are complementary and run in opposite directions. Count molecule types for a given number of base pairs. The string definition below specifies when two representations describe one molecule.

Formal Problem Statement

The alphabet is A , T , C , G , with complementary pairs A–T and C–G . Every letter has exactly one complement.

A molecule with \(n\) base pairs is represented by a string \(s=s_1\cdots s_n\) of length \(n\) . Its reverse complement is

\[ R(s)=\overline{s_n}\,\overline{s_{n-1}}\cdots\overline{s_1} \]

An overline means taking the complementary letter. Two strings describe the same molecule exactly when they are equal or one is the reverse complement of the other.

Each query gives \(n\) and asks for the number of molecule types modulo \(10^9+7\) . There are \(m\) queries; output only the bitwise XOR of their individual residues.

Input Format

The first line contains \(m\) . Each of the next \(m\) lines contains a query length \(n\) .

Output Format

Print one nonnegative integer: first reduce each query count modulo \(10^9+7\) , then take their bitwise XOR.

Samples

Sample 1

Input

3
1
2
3

Output

40

Sample 2

Input

4
1
1
2
2

Output

0

Sample 3

Input

1
4

Output

136

Sample Explanation

For lengths one, two, and three, the counts are \(2,10,32\) , so the first sample gives \(2\mathbin{\oplus}10\mathbin{\oplus}32=40\) . Each length occurs twice in the second sample, making the XOR zero. Length four has \(136\) types, giving the third sample.

Arrows apply reverse complementation. AA and TT form one class; AT is its own reverse complement. Each diagram counts as one molecule.

Constraints and Guarantees

For all inputs, \(1\le m\le500000\) and \(1\le n\le10^9\) . Queries may repeat.

Score share	Additional conditions
100%	None