In the Python language, converting a string to a list and then back to a str type results in a new string. The following console output describes this process.

Figure 1. Console output describing the string transformation process

We formally describe the transformation from $s$ to str(list(s)) as follows. To obtain str(list(s)), we replace each character $s_i$ ($0 \le i < |s|$) in $s$ with a string $t_{i,0}t_{i,1}t_{i,2}t_{i,3}t_{i,4}$ of length 5, generated by the following rules:

• $t_{i,2} = s_i$.
• If $s_i$ is not a single quote ', then $t_{i,1}$ and $t_{i,3}$ are both single quotes ' (ASCII 39); otherwise, $t_{i,1}$ and $t_{i,3}$ are both double quotes " (ASCII 34).
• If $i = 0$, $t_{i,0}$ is a space ' ' (ASCII 32); otherwise, it is a left bracket [ (ASCII 91).
• If $i = |s| - 1$, $t_{i,4}$ is a comma , (ASCII 44); otherwise, it is a right bracket ] (ASCII 93).

Now, given a string $s$ consisting of visible characters other than whitespace (i.e., all characters with ASCII codes from 33 to 126), let $s^0 = s$. For an integer $i > 0$, define $s^i = \text{str}(\text{list}(s^{i-1}))$. Given two integers $k$ and $p$, for each $0 \le j < p$, calculate the sum of the ASCII codes of all characters in $s^k$ whose indices are congruent to $j \pmod p$. String indices are 0-indexed. If no character exists at an index congruent to $j \pmod p$, the answer is 0. The answer may be very large, so you must output the result modulo $(10^9 + 7)$.

Input

The input is read from standard input. The first line contains a string $s$ consisting of visible characters other than whitespace ($1 \le |s| \le 10^5$). The second line contains two integers $k, p$ ($1 \le k, p \le 3,000$).

Output

Output to standard output. Output a single line containing $p$ integers, where the $(j+1)$-th integer represents the sum of the ASCII codes of all characters in $s^k$ at indices congruent to $j \pmod p$, modulo $(10^9 + 7)$.

Examples

Input 1

abc
1 16

Output 1

91 39 97 39 44 32 39 98 39 44 32 39 99 39 93 0

Note 1

The final string $s^1$ in this example is the same as $s^1$ in the Python console process described in the problem statement.

Input 2

abc
2 7

Output 2

472 420 580 408 474 439 429

Note 2

The final string $s^2$ in this example is the same as $s^2$ in the Python console process described in the problem statement.

Input 3

(See 3.in in the problem directory)

Output 3

(See 3.ans in the problem directory)

Note 3

The string in this example contains all visible characters other than whitespace.