18950번 - Hamming 다국어

문제

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.

입력

The only line of input contains a string $s$ of length $n$ (1ドル \le n \le 8 \cdot 10^{3}$) containing only characters "0" and "1".

출력

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円$.

제한

힌트