There are $2^n$ families living in a neighborhood, numbered from $1$ to $2^n$. Each day, every family sends a number of gifts to all other families, and this amount depends on the number of gifts that family received the previous day. Specifically, let $f_i$ be the total number of gifts family $i$ received on day $d$. On the following day, $d + 1$, family $i$ will send to family $j$ ($j \ne i$) a number of gifts equal to $f_i \times (2 \times (i \ | \ j) - i - j)$, where $|$ denotes the bitwise OR operation.
**Objective**: Given the number of families in the neighborhood and the initial number of gifts each family received on day $0$, calculate the total number of gifts each family will receive on day $k$.
### Input
- The first line contains two positive integers $n$ and $k$ ($n \leq 20; k \leq 10^9$);
- The second line contains $2^n$ non-negative integers, where the $i$-th number represents the initial number of gifts received by family $i$. These numbers do not exceed $10^9$.
### Output
- Print $2^n$ integers on one line, where the $i$-th integer is the total number of gifts received by family $i$ on day $k$, modulo $(10^9 + 7)$.
### Example
Input:
```
2 1
3 4 5 1
```
Output:
```
7 20 19 22
```
### Explanation
Each family’s gift calculation follows specific rules based on bitwise operations, as described in the input conditions.
### Subtasks
- **Subtask 1 (30 points)**: $n \leq 10; k \leq 5$.
- **Subtask 2 (30 points)**: $n \leq 10; k \leq 1000$.
- **Subtask 3 (30 points)**: $k \leq 10^5$.
- **Subtask 4 (10 points)**: No additional constraints.
