DZY владеет 2^m островами рядом с домом, острова пронумерованы от 1 до 2^m. DZY очень любит мосты, поэтому между некоторыми островами он построил мосты. Проход по одному такому мосту занимает у DZY один день.

DZY любит математику, поэтому все мосты он строил по следующему правилу. Для каждой пары островов u, v (u ≠ v) он построил 2^k различных мостов, соединяющих эти острова, где (a|b значит, что b делится на a). Все эти мосты были двусторонние.

DZY также построил некоторые мосты для связи его дома с островами. В частности, с островом i его дом соединен a_i различными мостами. Эти мосты односторонние, поэтому после того, как DZY пройдет по одному из них, дороги домой уже не будет.

DZY решил погулять по островам. В самом начале прогулки он находится дома. Затем DZY выбирает один из мостов, идущих от его дома. Так он добирается до некоторого острова. После этого он проводит на островах t дней. Каждый день он выбирает, остаться ли ему на текущем острове и отдохнуть, или же дойти по мосту до другого острова. На острове можно оставаться дольше, чем на день. Также разрешается пересекать любой мост более одного раза.

Предположим, что в момент времени сразу после t-го дня DZY находится на i-м острове. Обозначим за ans[i] количество способов дойти до i-го острова ровно за t дней прогулки по островам. Ваша задача — подсчитать ans[i] для каждого i по модулю 1051131.