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 ≤ n ≤ 4 · 10³) 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.

Original limitations in this problem were n ≤ 8 · 10³, TL = 25 sec, ML = 1 GB. Limitations were so big to try to ban solution with complexity O(n³). 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 :)