You are given a binary string *s* of length *n*. Compute the sum of pairwise Hamming distances between all subsequences of string *s* with length exactly *k* for all *k* from 1 to *n*. Since the answers can be very large, find them modulo 40 961.

Hamming distance between two strings of equal length is the number of positions in which these two strings are different.

### Input

The only line of input contains a string *s* of length *n* (1 ≤ *n* ≤ 4 · 10^{3}) containing only characters “`0`

” and “`1`

”.

### Output

Print *n* numbers: *k*-th of them must be the sum of pairwise Hamming distances between all subsequences of string *s* with length exactly *k*, taken modulo 40 961.

### Samples

input | output |
---|

11000110111001 | 48 4056 15326 31033 20654 29362 32472 13700 21357 12217 20411 12456 212 0 |

000 | 0 0 0 |

### Notes

Original limitations in this problem were *n* ≤ 8 · 10^{3}, TL = 25 sec, ML = 1 GB. Limitations were so big to try to ban solution with complexity *O(n*^{3}). I think that getting AC with that complexity is easier now, while getting AC with correct complexity is harder. I believe that you will succeed, but remember that it is not what we meant creating this problem :)

**Problem Author: **Alexey Danilyuk, Oleg Merkurev

**Problem Source: **Petrozavodsk Summer 2018. t.me/umnik_team Contest