During 3 days I couldn’t find appropriate way
to work with big binomials having lost of order
or overflow. Simple and clever routine was found and
gave satisfaction.

I congratulate. thanks for instructions (http://acm.timus.ru/forum/thread.aspx?id=19224&upd=633922277282410000).

Could you give any hint: what kind of "simple routine" have you found? I also have got overflow / lost of order? Is it possible to avoid such problem in O(N^2) solution?

I don't know what your algo is, but my dynamic O(N^2) solution hasn't problems with overflows - all numbers is of order N

Thanks! I've got AC with O(N^2) DP. Every value was not exceeding N. But it's still interesting - how did some people get AC with 0.015sec and minimum of memory.

I suppose there exists some formula, but it is not trivial (like in this problem: http://acm.timus.ru/problem.aspx?space=1&num=1762)