ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2122. Hamming

Time limit: 4.0 second
Memory limit: 256 MB
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 · 103) 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

inputoutput
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 · 103, TL = 25 sec, ML = 1 GB. Limitations were so big to try to ban solution with complexity O(n3). 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