1e9 대충 2^50이고 50xN dp 돌리면 안됨?