Matrix Product Sum with Bitwise Matrices

Given an integer n (n ≤ 512) and two integers seed_A and seed_B, construct two matrices \(A\) and \(B\) of size \(n \times n\) as follows for \(0 \le i,j < n\):

\( A[i,j] = \Bigl( (i \operatorname{or} j) + j \Bigr) \oplus seed_A \)

\( B[i,j] = \Bigl( (i \operatorname{and} j) + i \Bigr) \oplus seed_B \)

Here, \(\oplus\) denotes the bitwise XOR, while \(\operatorname{or}\) and \(\operatorname{and}\) denote the bitwise OR and AND operations respectively. The matrix \(C\) is defined as the product \(C = A \times B\) (using the standard definition of matrix multiplication). However, instead of outputting the full matrix \(C\), output the sum of all elements in \(C\) modulo \(10^9+7\).

inputFormat

The input consists of three integers: n, seed_A, and seed_B, separated by spaces.

outputFormat

Output a single integer, which is the sum of all elements of the matrix \(C = A \times B\) taken modulo \(10^9+7\).

sample

2 0 0

12