CSES 3141 ↗

And Subset Count

For each `k` in `0..n`, the number of non-empty subsets whose bitwise and is `k`, modulo `10^9 + 7`.

0
submissions
—
best score

You are given an array of n integers. Your task is to calculate the number of non-empty subsets whose elements' bitwise and is equal to k for each k=0,1,…,n.

Input

The first line has an integer n: the size of the array.

The next line has n integers a1,a2,…,an: the contents of the array.

Output

Print n+1 integers as specified above modulo 109+7.

Constraints

  • 1≤n≤2⋅105
  • 0≤ai≤n

Example

Input:

4
3 1 3 4

Output:

7 4 0 3 1

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AndSubsetCount/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.