5000 1 2 1 2 2 1 2 2 1 1 1 2 1 2 2 2 2 1 2 1 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 2 2 1 1 2 1 1 2 2 2 1 1 2 1 1 1 1 2 1 2 1 2 1 2 2 2 2 1 1 1 1 2 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 2 2 2 1 1 1 2 2 1 2 2 1 1 2 1 1 2 1 2 1 1 1 1 1 2 2 1 1 1 1 1 1 2 1 2 1 2 2 2 2 2 2 1 2 1 2 2 2 1 2 2 2 1 1 2 1 1 2 1 2 1 2 1 2 2 1 2 1 1 1 2 1 1 1 2 2 2 1 1 2 2 2 1 2 1 2 1 1 1 1 1 2 1 1 1 2 2 2 1 2 1 2 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 2 1 2 2 2 2 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 2 1 2 2 1 1 2 1 1 2 1 1 1 1 1 2 2 2 2 1 2 1 1 1 2 2 1 1 1 1 2 1 1 2 2 2 2 2 1 2 2 1 1 2 2 2 1 2 1 2 2 2 1 1 1 2 1 1 1 1 2 2 2 2 2 1 2 1 2 1 1 2 2 1 1 1 1 2 1 1 2 2 2 2 1 1 1 1 1 1 1 2 1 2 2 2 1 2 2 2 2 1 1 2 2 2 2 1 2 1 1 1 1 2 1 1 1 2 1 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1 2 2 1 2 1 1 1 1 2 2 1 1 1 2 2 1 1 2 2 1 2 1 1 2 1 1 1 2 1 1 2 1 1 1 2 1 1 1 2 1 1 2 1 2 2 1 2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 2 2 1 2 2 2 1 2 2 1 1 1 2 1 2 1 1 1 1 2 1 2 1 1 2 1 2 1 1 2 1 1 2 2 1 2 1 2 2 2 1 2 1 2 1 1 1 2 1 1 1 1 1 2 1 2 2 2 2 1 2 1 2 1 2 1 1 2 2 1 2 1 1 2 2 2 1 1 2 1 1 1 2 1 2 1 2 2 2 2 1 2 1 1 1 1 2 1 1 1 2 1 2 1 1 2 2 2 2 1 2 1 1 1 2 2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 2 1 1 2 1 1 1 2 1 1 2 2 2 2 1 2 1 2 1 2 1 2 2 1 1 1 1 1 1 2 2 2 1 2 1 2 2 1 2 2 2 1 2 1 2 2 1 2 1 2 1 1 1 2 1 2 1 1 1 1 2 1 1 2 1 2 2 1 2 2 2 1 2 2 2 1 2 2 2 1 2 1 2 1 2 1 2 2 2 1 1 1 2 2 2 2 2 1 2 2 1 1 1 1 1 1 1 2 1 2 1 1 2 1 2 1 2 1 1 2 2 1 2 2 1 2 1 2 2 1 1 1 1 2 2 2 1 2 1 2 2 1 1 2 2 2 1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 1 2 1 1 1 2 2 1 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 1 2 2 2 2 1 1 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 1 2 1 1 1 1 2 2 1 1 2 2 2 2 2 2 1 2 2 1 1 2 2 2 1 1 2 1 2 1 1 2 2 2 2 1 1 1 2 2 1 2 2 2 1 1 2 2 1 1 2 1 2 2 2 2 1 2 2 1 2 2 2 2 1 2 1 1 1 1 1 1 2 1 1 2 1 2 2 2 1 2 2 1 1 2 2 1 2 1 2 1 1 1 2 1 2 2 1 1 1 1 2 1 2 2 2 2 2 2 1 1 2 2 1 1 2 1 2 2 1 1 2 1 1 1 1 2 2 1 1 2 2 1 1 2 1 2 2 1 1 1 2 2 1 1 2 2 2 1 2 1 1 2 1 2 1 1 1 1 2 2 1 2 2 2 1 1 1 2 2 1 2 1 1 1 2 2 2 1 2 2 1 2 2 2 2 1 2 1 2 2 2 1 2 1 1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 2 2 1 1 2 2 2 1 2 2 1 2 2 2 2 2 2 2 1 2 2 1 2 2 2 1 2 1 1 2 2 1 1 2 1 1 1 2 1 2 1 1 1 1 2 1 1 1 2 2 2 2 2 2 1 2 1 1 2 1 1 2 2 1 2 1 2 2 1 2 2 2 1 2 2 1 2 2 1 2 1 2 2 1 1 1 1 1 1 2 1 1 1 2 2 1 2 1 2 1 2 1 2 2 1 2 1 1 2 1 1 2 1 2 2 2 1 1 1 2 1 2 2 1 1 2 2 2 2 2 1 1 2 2 2 2 1 1 2 2 1 2 1 1 1 2 2 1 2 1 2 1 1 1 1 2 2 1 2 1 1 2 1 1 1 1 1 2 1 1 2 2 2 2 2 1 2 2 1 2 1 1 1 1 1 2 1 1 1 2 1 2 1 1 2 2 2 2 1 1 2 1 1 1 1 2 1 2 2 1 2 1 2 2 1 1 2 1 1 2 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 2 2 2 2 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 2 1 1 2 2 2 2 2 1 1 1 2 1 2 1 1 2 2 1 2 2 1 1 2 2 2 2 2 1 1 2 1 2 1 2 1 1 2 1 2 1 2 2 2 2 1 1 1 1 2 1 2 2 2 2 2 1 2 2 2 2 1 2 1 2 2 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 1 2 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 2 2 2 2 1 2 1 2 2 1 2 1 2 1 2 2 1 1 1 2 1 2 2 2 1 1 2 1 1 2 2 2 2 2 1 1 2 1 1 2 2 2 2 2 1 2 2 1 2 2 2 1 1 1 2 2 2 2 1 1 1 1 1 2 2 1 1 1 2 2 2 1 2 2 1 2 2 1 2 1 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 1 1 1 2 2 1 2 2 2 1 1 1 2 2 1 1 1 1 2 1 1 1 2 2 2 1 1 1 2 1 2 1 2 2 2 2 2 2 2 1 2 1 2 2 2 2 1 1 1 2 2 1 2 1 1 1 2 2 1 2 1 2 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 2 1 2 1 1 1 2 1 1 2 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 2 2 1 1 2 1 2 2 2 2 1 2 1 1 1 2 2 1 2 1 1 2 2 1 2 2 2 2 2 2 2 1 1 2 1 1 2 1 1 1 1 2 2 1 1 1 1 2 2 1 2 1 1 1 1 2 2 2 2 1 1 2 2 1 1 2 1 1 1 2 1 2 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 2 2 1 2 2 1 1 2 2 2 1 1 2 1 1 1 1 2 1 1 2 2 2 2 1 1 1 2 1 2 1 2 2 1 1 1 2 2 1 2 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 2 2 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1 2 2 1 1 1 2 2 1 2 2 2 2 1 2 2 1 2 2 2 2 1 2 2 1 2 1 2 1 1 2 2 2 2 2 2 1 1 1 2 1 1 1 1 2 2 2 2 1 2 1 1 2 1 2 2 1 1 1 1 2 2 2 2 1 1 1 2 2 1 1 2 2 2 1 2 2 2 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 2 2 2 2 1 1 1 2 2 1 2 2 2 1 2 1 1 1 2 2 1 2 2 2 2 2 2 1 2 2 2 1 2 1 2 2 2 2 1 1 2 1 2 2 2 1 2 2 1 2 2 2 2 1 2 2 1 1 2 2 2 1 2 1 2 1 2 1 1 1 1 1 2 1 2 2 2 2 2 1 1 2 1 1 1 2 2 1 1 2 1 1 1 1 2 1 2 2 1 1 1 2 1 2 1 1 1 1 2 1 2 2 2 2 1 2 1 2 2 1 2 2 1 1 1 1 2 2 1 2 2 2 2 1 1 1 2 2 2 2 1 2 1 2 1 1 1 2 1 1 1 1 2 2 1 1 2 1 1 2 1 1 1 2 2 1 2 2 2 1 1 1 2 1 1 2 1 1 2 1 2 1 2 2 2 2 2 1 1 1 2 1 1 1 1 1 2 1 1 2 2 2 1 2 1 1 2 2 1 2 1 1 1 1 1 2 2 2 2 1 2 2 1 1 2 1 2 2 2 1 2 1 1 2 2 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 1 2 2 1 1 2 1 1 2 2 1 1 2 2 1 2 1 1 1 2 2 1 2 2 2 2 2 1 2 2 1 1 2 2 2 1 1 2 1 2 1 2 2 2 2 1 1 2 1 1 1 2 2 2 2 1 1 1 2 2 1 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 1 2 2 2 2 1 2 1 2 1 2 2 1 2 2 1 2 2 1 1 1 2 2 1 2 1 1 1 2 2 2 2 1 2 2 2 1 2 1 2 2 1 1 2 1 1 2 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 2 1 1 2 2 1 1 2 2 1 1 2 1 1 1 1 1 1 1 2 2 1 2 2 1 1 2 2 2 2 2 1 1 1 2 1 1 1 1 1 1 2 1 2 2 1 2 1 2 2 2 1 1 2 2 2 2 1 2 2 2 1 1 2 2 1 1 2 1 1 1 2 2 2 1 1 1 2 1 2 1 1 1 1 1 1 2 2 1 2 1 1 1 1 2 2 1 1 2 1 1 1 2 2 2 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 2 1 1 1 2 2 2 2 2 2 2 1 1 2 1 1 2 2 2 1 1 2 2 2 2 2 2 1 1 1 2 2 1 2 1 2 1 2 2 2 1 2 2 1 2 1 1 1 2 1 1 2 2 2 2 2 2 1 1 1 1 2 1 2 1 1 1 2 1 2 1 2 2 2 1 2 1 2 1 1 1 2 1 2 2 1 1 2 2 1 2 2 1 2 2 2 2 1 2 1 1 2 2 2 1 1 2 2 2 2 2 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 2 1 1 2 2 2 1 2 2 2 1 2 1 1 1 2 2 2 2 1 1 2 2 2 1 1 1 2 2 2 1 2 2 1 1 2 1 1 2 2 2 2 1 1 2 2 2 1 2 1 2 1 1 1 2 2 1 1 2 1 1 1 1 1 1 2 1 2 2 2 2 2 1 1 2 2 1 1 2 2 2 1 1 1 1 2 1 2 2 2 2 2 1 2 1 1 2 2 1 2 2 1 1 2 1 1 1 2 1 1 1 2 2 1 1 2 2 1 1 1 2 2 2 2 1 2 2 2 2 2 1 1 1 1 2 1 2 1 1 2 1 2 1 2 1 1 2 1 2 1 2 2 2 1 2 2 2 1 2 2 1 2 2 2 1 1 2 2 1 2 1 2 2 2 1 2 1 2 2 2 1 1 2 1 2 1 2 2 2 1 1 2 1 1 2 1 1 1 1 1 1 2 2 2 2 1 1 2 2 2 2 1 1 1 1 2 1 2 1 1 1 2 1 1 1 2 2 1 2 1 1 1 2 1 2 2 2 1 1 1 2 1 2 1 2 2 2 2 2 1 1 1 2 2 2 2 1 1 1 2 2 2 1 2 2 2 2 1 2 2 2 1 1 2 2 1 2 2 1 2 1 2 2 2 1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 2 1 2 1 1 2 1 1 2 2 2 2 1 1 2 2 2 1 2 2 2 2 2 2 1 1 1 2 1 1 2 2 2 1 2 2 1 2 2 2 2 1 1 1 1 1 1 2 1 2 2 2 1 2 1 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 2 2 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 2 2 2 1 2 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 1 2 1 1 2 1 1 1 2 2 1 2 2 2 1 1 1 2 1 2 2 1 1 1 1 2 2 2 1 1 1 2 1 2 2 1 2 1 1 1 1 1 2 1 2 2 2 2 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 2 2 1 2 1 1 2 2 1 1 2 2 2 2 2 2 2 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 2 1 1 2 2 1 1 2 2 1 1 1 1 2 1 2 2 2 1 2 2 2 1 2 1 1 2 1 2 2 1 1 2 1 2 1 2 1 1 1 2 2 1 2 1 1 1 2 1 1 1 1 1 2 2 2 2 1 2 2 2 1 2 1 2 1 1 1 1 2 2 1 1 2 2 1 2 1 1 2 2 1 1 1 1 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 2 1 2 1 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 2 2 2 2 2 1 2 1 1 2 2 1 1 1 1 1 2 2 1 1 1 1 2 1 2 2 1 2 2 2 2 1 2 1 1 1 2 1 2 1 1 2 1 2 1 1 2 2 2 1 2 1 2 1 1 2 2 2 1 2 1 1 2 1 1 1 2 1 1 2 2 2 1 2 1 1 2 1 2 2 1 2 2 2 1 2 1 1 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 2 2 1 2 2 2 2 1 1 1 2 1 2 2 1 1 1 1 1 2 1 1 2 2 2 1 2 2 2 1 1 2 1 2 1 1 2 2 1 1 2 2 1 2 1 2 2 1 2 2 1 2 1 2 1 2 2 1 1 1 1 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 1 1 2 2 2 1 2 2 2 1 1 1 1 2 1 1 1 1 1 1 2 2 2 1 1 2 1 2 1 1 1 2 2 1 1 2 1 1 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 1 2 2 1 1 1 1 1 1 2 2 2 1 1 1 2 1 1 2 1 2 2 2 2 2 1 1 1 1 2 2 1 1 2 1 2 1 1 2 2 2 2 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 1 1 1 2 2 2 2 2 2 1 1 2 2 2 1 2 1 1 1 1 2 2 2 1 2 1 2 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 2 1 1 1 2 1 1 2 2 1 2 2 1 2 2 2 1 1 1 1 2 2 2 1 2 1 1 1 2 1 1 1 2 2 1 2 1 2 2 1 1 1 1 1 2 2 2 1 2 2 1 1 2 1 1 1 1 2 2 1 1 1 1 2 1 2 1 1 2 1 1 1 2 1 1 2 2 2 2 2 1 2 1 1 1 1 1 2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 1 1 1 1 2 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 1 1 1 2 2 1 2 1 2 1 2 1 2 1 2 2 2 2 2 2 1 1 2 2 2 1 1 2 2 2 1 1 1 1 1 1 1 2 2 2 1 1 2 1 2 1 2 2 2 2 2 1 2 1 2 2 1 2 2 2 2 2 1 1 1 2 1 1 2 1 2 2 2 1 1 1 2 2 2 1 2 2 1 1 1 1 2 1 2 1 2 1 2 1 1 1 1 1 2 1 2 2 2 1 2 1 2 2 1 2 2 1 2 2 2 1 1 1 2 1 2 1 1 1 1 1 2 1 2 2 1 1 1 2 2 2 1 2 1 2 1 2 1 2 1 2 1 2 2 2 1 1 2 1 2 1 1 1 2 2 1 2 2 1 1 1 1 1 1 1 2 1 2 1 2 2 2 1 2 2 2 1 1 2 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 1 1 1 2 1 2 2 1 1 1 2 2 2 2 1 1 1 1 1 2 1 2 2 2 1 2 1 2 2 1 2 1 1 1 1 1 2 1 2 2 1 2 1 1 2 2 1 1 1 2 2 2 1 2 2 2 1 2 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 1 1 1 1 1 2 2 1 2 1 1 2 1 1 2 1 2 2 2 1 2 2 1 2 2 1 1 1 2 2 2 2 2 1 2 1 1 2 1 2 2 2 2 2 1 2 2 2 2 2 1 1 1 2 1 2 1 2 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 2 1 2 1 1 1 2 2 2 2 1 1 2 1 1 2 1 1 1 1 1 2 2 2 2 1 1 2 2 1 1 1 1 1 1 2 2 1 1 2 2 1 2 2 2 1 2 2 1 2 1 2 1 2 2 1 2 2 2 1 2 1 2 2 2 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 2 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 2 1 2 2 2 2 2 2 2 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 1 2 2 1 1 1 2 1 1 2 1 2 1 2 1 1 2 1 2 1 1 2 1 2 2 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1 2 1 1 2 1 1 2 2 1 1 2 2 1 1 1 2 1 2 2 2 2 2 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 1 2 1 2 1 2 1 2 1 2 2 2 2 2 2 1 2 2 1 1 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 1 2 2 2 2 2 2 2 2 2 2 1 2 1 2 1 1 1 2 1 2 1 1 1 2 1 1 2 2 2 1 1 1 2 1 1 1 1 2 2 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 1 2 1 2 2 2 1 1 1 2 1 1 2 1 1 1 1 1 1 2 1 2 1 1 1 2 2 2 2 2 1 2 2 1 1 2 2 1 2 1 1 1 1 2 1 2 2 2 2 1 2 2 1 1 1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 2 1 2 1 2 2 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1 1 1 2 2 1 2 2 1 2 1 1 1 2 2 1 2 1 2 2 1 1 1 2 2 1 2 2 1 2 2 1 1 1 1 2 2 1 1 2 1 1 2 1 2 1 1 1 1 1 1 2 2 1 1 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 1 1 2 2 2 1 2 2 2 1 2 1 1 2 2 1 2 1 1 1 2 2 1 2 2 2 1 1 2 2 2 1 1 1 1 1 2 1 1 1 2 2 2 1 2 2 2 1 1 1 1 2 1 2 2 1 1 2 1 1 1 2 1 1 1 2 2 1 1 1 1 2 1 1 1 2 2 2 1 2 2 2 1 2 2 2 1 1 1 1 2 2 2 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 2 2 2 2 1 2 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 2 2 1 1 2 2 1 2 2 2 1 1 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 1 2 1 2 2 2 2 1 2 1 2 1 2 1 1 1 1 2 2 1 2 1 1 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 2 1 1 2 1 2 1 1 1 1 1 1 1 1 2 2 1 2 2 1 2 1 2 1 1 2 1 1 2 1 2 1 1 1 2 2 2 2 1 2 2 1 2 1 1 2 2 2 1 2 2 1 1 1 2 1 2 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 1 2 2 2 2 1 1 2 1 1 1 1 1 2 1 1 2 2 1 1 2 2 2 2 2 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 2 1 1 1 2 1 2 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 2 1 2 2 2 1 2 1 1 1 1 1 1 1 2 2 2 1 1 2 2 2 2 2 1 1 2 1 2 2 2 2 1 2 1 2 1 1 2 1 1 2 2 2 1 1 1 2 1 1 2 1 1 2 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 2 1 1 1 2 1 2 1 2 2 2 1 2 2 2 1 2 2 1 2 1 1 2 1 1 1 2 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 1 1 2 2 1 1 2 1 1 2 2 2 2 2 1 1 2 1 2 2 1 2 2 1 1 1 2 1 1 2 2 1 1 1 2 2 2 1 2 1 1 1 2 2 2 1 1 1 1 1 2 2 1 2 1 2 1 2 1 1 1 1 2 2 1 1 1 2 1 1 2 2 2 2 2 2 1 1 2 2 2 1 1 2 1 2 2 2 1 1 1 1 2 1 1 2 2 1 1 2 2 2 2 1 275988115 35891452 484474923 977899815 951757367 810698436 125258724 455623045 380817496 148041442 275347039 455382113 885536842 554536983 901302291 910878573 139340229 616115751 679139354 512681378 683363685 207814748 757817010 509368761 614358315 646446084 983633852 589839539 83590906 340261102 415771968 42378834 961805595 97396721 595604967 582465437 61545145 915272038 744854911 515493728 758404710 741173161 269588347 210644137 18366100 470347163 209460081 861622604 786401309 816927523 526306714 634223201 927435964 529147304 53658965 52568769 302075282 195447961 403154340 482693516 730961314 806953445 647325613 184281253 96407636 163027075 956115770 979839796 967733238 266076908 581364026 504420387 763229238 277083036 63460414 982452386 126204585 630934932 751595772 155937444 896927048 885037787 188935376 686816095 663508206 368395512 813778998 468495312 600389083 361011066 701493585 557426485 896231988 114626160 259592808 95706513 832725120 502978801 210096739 156602411 138359852 463940502 458937170 902318095 641806856 189875451 182874854 291484299 295475401 379894338 428833526 603733428 124207493 623178127 132861948 908196063 817926202 85379213 205733270 955052840 313971783 701949671 579069189 71332334 219032816 155019472 781589425 737901397 520984030 777282428 458611106 113254594 977574813 433762724 254821385 495249763 847653917 433029638 103398325 887936677 224063794 970149347 2266015 397176508 226324756 849683840 556879199 717299486 318090464 959939749 9244595 140814088 440663828 654711585 11099903 250704888 626764823 357128004 308444104 361086001 128764079 862899299 270613816 821029690 302393480 246817623 325204894 235556959 830808244 147782398 130189034 336614190 908752422 369753273 463133493 274003964 818083382 628877549 734638391 643206750 460890400 294011778 475460815 410196400 240146052 225108583 284950911 159596433 530763751 75269131 472809198 529323621 280230705 215906790 219032932 974733266 249985326 808375022 640613969 842287427 621873677 546024994 879918278 152788584 62677476 233113347 841688058 591349172 580320553 471595030 186607558 243541726 801164090 927041379 643593002 386531681 522263767 430268665 782913734 19311867 167687843 944899944 349994337 95063601 255584166 129129541 756120166 994742474 764971981 515196073 102685282 279880272 549238377 453043634 452661640 402350226 262537388 991213313 105548845 513158181 290853423 981659451 587807563 232866526 864807791 233503881 98013442 691408985 776569931 459177751 375389971 652038774 621837448 585234840 397744995 994434006 494583885 608944064 154459774 59750498 196685479 218540233 629854738 150991813 266323462 974395887 591739759 267314669 888199870 962036980 115296782 444371854 715608456 182049437 57881095 77493919 332822014 443389746 785956505 138802394 250034978 470470402 442286246 861212736 776059351 670639325 102560052 814731667 917191014 887207064 277765101 503768283 20562427 20859789 938422176 929034210 338640166 451110168 772143806 532382392 42727003 826755355 837379037 3209263 753160562 634703482 95942201 241992799 403101479 258276768 870132782 898453796 771078555 913258745 886877631 964019355 802877649 208119158 494341906 796697513 391828786 894019852 950647538 13675124 21436938 253869877 493560140 674588391 277063688 774355309 169962930 622888242 403110338 409918902 374131675 290543688 340925487 263231764 574171681 179890272 155856683 113070098 494596609 299517301 828785654 233925948 762200223 553205190 316974517 888618403 747524927 736756822 344967152 899817820 825816525 11157357 808839442 700371457 975829334 550859541 699761901 700997422 599560333 918404510 365354291 340651781 841933895 252669466 161013758 971657899 273145343 170730721 545121353 717646536 433390163 106027535 775371380 937251851 299977604 323040769 885903044 909254052 5755898 343007708 555095520 602170313 593561278 446218758 6314837 283379249 670872575 838069931 589640211 589766300 984950670 335435833 448994543 887071049 906812257 424008164 514790687 267679613 90562579 629846051 369171649 411098115 307146594 468780849 266641748 129287591 116403888 841675661 796603452 484901306 882987396 403808890 833103682 598545041 988149766 587678336 981854482 321083398 527371142 284108265 796426684 214862325 106562805 275258693 673883956 63697600 506826602 551704038 364367826 956725708 481058462 870986853 281615571 281260546 191063920 66123547 163465942 542329935 67226211 793192105 122911839 745743396 507810331 543289456 695131223 692760054 7854564 857350938 980862090 567296959 655811627 424433935 625235495 473503099 715891458 457281793 788741700 835270572 757956768 242814049 332805208 959261655 145794015 310651367 46235327 577702661 915861181 101022221 592916794 742158403 152535259 932841877 319738732 557999906 770250241 999453183 728399198 208348215 192218264 826640404 238031355 221158300 691953710 512116830 92505493 548724590 964079094 941313453 802820190 93997133 156462917 663331219 739577584 485708255 512051222 190933737 219970758 880075596 471782279 67050568 439058624 505216451 571298906 790998673 167948195 581763828 496260981 355587430 954029207 373955989 255157346 828055470 544478119 316772830 310660048 809121813 444654661 127028236 796471824 1592201 434993603 758812897 790283672 495404990 435970522 728104994 887115652 699499947 876572967 268855576 448751120 765041675 990122409 699248912 618621215 42360285 952445765 927811035 313075383 73108197 652648514 167896654 688827267 679430185 639522253 639524547 108502352 224393844 830109302 187267991 310405008 843542742 519782578 921956778 330782170 792132897 466632535 835577570 987579496 16023150 574010914 236383400 886592151 853941654 188553268 944906345 802653546 895351738 926195857 939164694 910177288 592364220 447304864 343191716 830892602 194517443 48686254 554402957 38644462 346326459 461232747 956468814 314565302 723065811 252472682 239298791 138702922 359909373 163787173 800933470 470150914 288441713 754537976 807899196 713679196 103683370 148024482 963687438 287486332 86526055 729937351 717743589 304173479 906152236 79363568 795781335 238814919 60852414 559830152 2148732 543226602 390877227 857594465 284748401 868151747 38095552 918726190 521006296 587036456 641837200 353530630 690426582 159964562 553752308 625620200 668602388 167508640 474216198 88935729 952107583 361379732 243741220 490437415 147554185 209725908 649976947 156672114 56870693 712821098 358496602 955708829 678900174 422414725 338590211 752714394 561352769 953829622 107732957 701015355 896813502 366427316 165466396 46003642 831345291 789879896 404237624 531383090 444086385 529821858 20072810 580041763 955867453 168597490 526847794 489985266 154104128 524075727 241400019 388343398 774732240 762694756 334853589 376515116 876570565 387394302 978227587 326787925 694575612 287757967 794991979 282591955 532329944 962919726 782931425 507009023 471424444 340877205 148999803 233061142 232326034 960256418 228214934 920167351 4168519 787154134 680835536 259508070 409413452 823617753 964274828 553459725 81409815 948306420 729368177 965958774 601623456 230412181 427631339 504800978 777128420 337218767 704417193 168539957 728919910 98932951 206674717 651709975 105632425 590942600 158994687 339190484 18792375 801821152 612569802 797432877 788505757 56164993 55841342 684356294 516112876 863487537 293989852 596657062 772022074 600702042 959026541 34358457 501928351 85815690 293959292 366730577 260992057 59848180 369776343 650989729 260690600 140210670 880188690 272015937 811996050 104144497 234660611 108209325 674857760 975862172 348349511 73503174 931663231 724389682 610587836 10941263 1397089 367596823 646065925 495906673 418675833 852602838 382184202 415778615 855374850 870960926 268974709 88315155 368489785 238827584 628534581 128664407 422538206 77022899 344414207 671021245 222549176 716253841 970534600 347461856 911011854 636732183 455015756 61367488 182013486 471627049 917328267 433382210 981984745 405590987 831560774 383087534 495542549 918683305 554862470 228587567 345478922 173337744 378154262 605552215 72206630 793973746 347648260 953096088 154128201 596365159 957233188 244104140 848613465 873014822 292206221 320352685 101422784 205511824 146176025 824207709 457454825 837606566 478953 409286880 112882630 296476302 470916063 117419678 519885133 356886290 944424739 814997474 171120374 479976480 512712863 938420573 260803135 563146571 683560067 328449955 842682152 278293576 970924993 503848876 253323448 920832882 616963730 796600149 777379702 21666375 527167727 395319773 824577520 382582249 976687896 167451752 848305463 120257438 194177553 20072063 664021345 638530385 919525408 311209102 461791750 639444494 292747089 558285413 973231812 849560714 993887218 651271608 855517116 978154392 681306391 346595487 580877330 994309813 995745559 278458903 220151408 901311613 15750669 844392062 577865091 117286707 152283224 928126491 213583485 367267646 540222747 958583700 67800978 539786150 555670717 55763061 192403579 597721755 879164267 170506672 130384630 556906478 180882321 416336408 199114563 726445462 110185573 276813028 78256296 407854125 182789212 300751411 31869423 687948145 759786931 678802306 483082723 213676739 70394599 630366263 106752471 285000107 300698941 121254426 816332830 482206290 554371387 460677078 613596308 494433798 492150573 485884285 113984787 695991226 404557729 712165121 71241727 398481539 254537195 654067388 761280699 868928540 983678114 248531433 346940978 530823011 261016097 775215912 97218895 923899610 372180231 13097214 341327748 662118182 125789879 385989202 810764103 727144340 448224729 609323250 596192913 127860879 298415319 984571916 738974557 161628203 745214561 95240885 60247087 198165150 643314153 906850406 905584266 342990529 494315560 920450425 982322553 942132883 290166167 889955760 402357255 681522102 68119287 921859247 377541575 784803312 302320074 200130173 747513676 823851436 441120471 117908487 862059698 817962102 68858026 321758621 651031572 563752323 6677009 11096947 887595027 31178279 883096224 495124514 296579670 867218524 878618926 797156644 25859588 748785986 359479382 405593435 299462219 575167385 725838583 990350218 174703837 346407496 40453301 839340762 683540078 502902490 162587253 533900631 592781111 924724220 575913189 221743729 925042550 697910273 689738993 24372092 575528940 130964830 63652431 408575024 917490269 921034030 198934517 25271081 900081684 540088750 447409821 97741416 556800092 185521858 581117768 531078096 301759752 508355183 430159800 747211178 859806444 883552607 937645812 250848545 426424417 781982048 282849736 509704391 217360325 852719077 678794050 294125327 15761913 11312771 403624758 874857680 527421665 959923573 42482363 684280264 345544679 925019161 272585388 449871639 116323961 843838833 309625385 828547008 461544583 705241763 473617683 574490411 747410182 753127802 812021907 918239654 905927279 935863010 633549203 503820511 848770880 500895599 796797763 433608811 763225722 231535575 17335190 227246147 650385953 989930867 451806146 36859714 905235392 179364547 652741828 105558440 164724450 22728679 293692378 383622554 535063962 306214182 508097798 708217759 706241788 939187563 101903762 986037540 145631137 3292355 567961223 677647098 962775591 35475168 255676212 121149907 727391151 64631193 533355949 953035976 168436317 817055592 886855497 585152470 367687132 572903914 687687460 419518556 694998999 685659747 784531611 282033054 630293121 623152183 776466386 766209349 315537678 428628338 618606129 843673053 204353592 280720193 488294627 83871574 817047227 835642487 132341590 294674308 112747480 683073033 858303933 836577439 530343382 97201042 439859089 501580740 851863165 881865680 59491340 118343025 573602713 73638181 898144940 439353869 683253117 484064279 800361910 21635678 132574077 164974544 283717809 891251728 877564018 416732318 137223911 894675509 53797690 449166964 594042343 858104256 689513270 235528040 754740741 86626313 689405131 669925939 923049177 34318668 709158369 791425204 991276988 237501737 476819047 112567405 83054158 348828965 295308493 410594052 221564147 746258728 363376264 952348867 993408337 767416830 970420881 287124761 514372307 76157398 814377447 467820311 552741673 614940358 393959432 543635444 774292166 605906244 582989692 293842826 808149345 243615406 238887498 602207446 674559092 511208900 101628545 231560315 370505152 166068009 824143025 710554432 370103239 311422437 46540911 138284174 624058961 84919269 844688085 12189939 161571048 763888250 54832383 434426529 357772635 235601110 79981711 218507759 611377215 867794066 59801129 264793047 683494249 587756075 810826232 378487415 895412341 845135232 633268263 874852752 292934466 842832470 231601513 656940298 594641012 845839060 413914994 892495214 441314801 775085063 171746684 60481130 322476389 627304031 482140355 293151057 208588990 95488560 148043529 547922840 255979696 624567347 494102291 601980762 294439729 813027842 509903145 934597077 276801022 786107551 706322330 784408043 144717589 556408045 680247094 899530914 495829817 445652534 388967378 293730725 740839538 322322595 349350088 737922496 417354890 405548487 197874036 602062183 918216592 766872341 387745720 222341424 32827993 841329253 749131897 480253524 245741818 420682867 619098143 763473714 73185615 650145632 131097369 393719757 574035832 802720559 730397271 333872201 933106774 753278025 632918478 135214961 802113042 588564474 210333944 840837940 904720535 385457393 610336593 228679460 341067283 297765828 292220123 561368310 133486970 513329002 345110683 636775684 420399875 571967423 374094617 481952974 774097065 281103875 300929764 198400884 619453611 16121691 626650892 938007614 491261452 852916047 173272998 215469845 689473300 968827978 184186956 698844423 255057357 409225246 622970010 467018950 514823302 748999293 553898674 331654442 720927828 713478529 813141945 274245546 338247564 630400037 585376856 975337703 738456139 594798793 27633980 455498018 777240814 758021042 364763029 122322113 852993690 227825031 354433435 282955470 395440053 394019797 474572037 30344567 511464042 491588492 736904080 252279951 256069930 787645313 760352638 907080716 481201958 202071274 207893012 235866247 520569046 825172965 884907034 567305663 197668981 686844913 19606111 119914262 712237698 616576114 364136499 914579986 660483648 581407537 36585451 584201950 222034486 393105626 667113825 188502726 525205169 927527293 83596402 454746814 159968317 777875214 460414334 811274716 328489520 553245669 582619114 68850138 381384991 9450815 261744289 819803029 516032359 172812219 941443215 743174544 715660709 274201053 144213285 786111602 608045374 470895758 60930776 781336451 130198232 564726170 32562082 502118195 100265183 664189488 768121728 968833428 471273473 776918374 448444658 503880411 787448242 724033715 350595453 880321507 568855209 444895347 417794604 162725545 597869409 995069543 607623691 44084945 225554073 857992242 281389227 381596704 993666517 311319517 194275490 716235519 764387290 684555859 402433031 382402303 773645110 688496614 981646074 970833743 389518517 99248840 242026522 292470088 551531501 166648723 480236813 415884002 191314868 383107522 210926332 863137084 98226852 723159093 91834644 544163096 99588510 278103473 241173766 549221212 391052355 395156318 468620679 462732178 532011901 352888135 93739729 777443432 876450804 79999710 9078560 159215665 779745434 297481589 99884854 248975203 431170848 172475589 977652952 764273943 588324478 625981291 863989583 626331021 649522543 96417638 426233832 572463781 461225202 392277147 739144820 297644134 387059915 726974289 845846473 690359674 649737727 366216373 324859967 870425008 402174300 597936471 17958451 557117050 17915886 667813292 325736071 196913516 952764299 533622922 145032992 301247683 456671049 912213422 187392359 674121692 688403458 92648505 615260873 519563704 876998359 697932591 804811063 944265087 653263274 131954167 802561959 873214201 401288610 174405854 809148049 673289494 219031467 688897940 454465138 567632488 931219187 623795628 750500428 151477156 676254063 953190689 704968740 805806629 456611924 347496140 845359491 130772585 146685598 352632047 769065462 770084498 487102348 304777645 5761422 741959909 783422753 40824207 419917665 856781390 189772965 642758144 126500871 824991451 987951395 798500306 893176349 935709245 854097385 428959672 316055750 418845258 438276362 490801865 642748453 172382077 233321951 806089988 611647460 931962740 592761217 503094726 904310704 280264561 188699473 339461205 802594746 344022746 705206641 313959001 462873911 196960186 669844297 139787869 246173409 555444029 705145346 680044115 153173877 729006136 742397198 384694797 88638515 249279902 341633182 898442181 820579681 302001932 191575082 966014102 141384904 50427710 13535981 835516672 316216373 914522263 196154471 403565416 677553145 105189278 682466521 395709589 275081066 643423611 750319564 673201204 224944480 288839806 584832139 400674646 642220217 895749273 790709924 942193389 315927765 727949793 522099306 55447634 201328666 410435345 934169462 605177794 981528177 389862918 569871650 994864348 184430023 490332740 623863565 329577764 794963085 475782511 647124890 428331652 129014329 412365267 450954352 52987846 69201347 156861661 706361083 515361051 93543977 568290720 386236137 122032279 856536811 332510034 72503983 79285938 585372815 144417740 145681922 852591304 882928414 504983052 914230878 463465882 220455589 87677622 87159171 1634252 794231222 868569743 841093106 287317605 149473764 159759617 680890228 353111889 266174026 672799899 692967316 212255714 254691845 897236878 365768224 154293579 961711797 672676400 511558059 891592484 686103296 788873085 985703950 944270825 261522703 996488081 405893347 354297723 293106448 65302063 94725641 633642397 640698802 982999357 803483683 249108088 140061868 490329926 909535512 158956823 39515958 284546039 3056276 377600492 789120141 266135202 159081094 589003081 394793076 450339006 685341088 82805224 681770414 278584932 872561115 677532004 278698629 571279060 708504816 440492733 936735046 489162478 839917279 404130008 724148931 156551098 53198444 307215613 841433807 369493728 780206493 458663767 678074565 603380528 179311678 700415864 290759170 983391004 526776413 121258194 638042215 642340665 938148558 369127743 190063832 531060930 121808295 809550201 738777023 555534869 985711301 852223395 261109129 264400691 137919558 289038782 57967912 914031172 434372877 665204789 491427471 527776785 492066114 361513042 16530233 167580809 534982351 982666438 454345891 3423036 894086628 421762085 907549390 180686307 187822963 336040807 825983166 931534038 210810804 475502697 834626301 921789332 787650211 517781610 303873048 83817279 206523005 612220046 114317601 829023005 345835079 616524382 589782571 968274712 477029959 548451910 965743314 40604223 418053257 644358678 591050928 953330499 552124251 896561538 733974505 145865467 666953681 871164578 89939872 747786464 415733314 572065907 778797695 851715985 992287432 235263315 236897588 173881169 528856516 837558153 103130862 348567684 440263257 278227899 233212388 249943606 753085164 496057717 937040846 150454932 177436586 257877417 78715498 758532464 912739074 993036586 343218168 996326081 123850279 892707119 571914687 378929441 261128079 660938199 644655750 492338765 962774902 667431583 562972955 34714025 664906332 224907501 441520336 439481529 959085955 591928969 314289145 441278377 975110514 326586910 732920943 936687558 271374452 558665150 781962256 385011715 605213466 9346395 452295996 913046389 702941365 801908559 619907418 50131415 18612189 730770133 704052561 314846727 452636397 730075789 777413135 744402055 617705604 127797500 607645446 962300925 317160453 355501834 636863658 67965875 4215832 812286082 576337140 960640536 709972775 534229141 8013794 9699645 484973026 864711255 374624244 283305816 15586747 551646017 657686193 147876164 205276523 88636845 451340064 304971008 222898539 710391645 669302863 320547372 95588988 793087477 646272464 378471055 431647776 80318844 620532279 231369363 358083358 30508767 131563933 482530759 708349441 85626478 421221920 512941916 245788570 515981405 681214049 839161513 740572026 839174469 538688004 8081832 811496569 44527776 36560435 397114742 398012210 520660304 173515292 278876886 499061892 818958872 12097390 93545647 497104402 777691681 290414304 37043338 914987204 12188023 848030379 115988757 798049604 345161098 829561098 783563426 113937538 270539182 299931841 368402856 846170161 254565787 199405460 26300737 976197959 488269805 920063179 465278891 37794433 693111461 771994036 604310215 276445917 665628070 179860001 259891869 470125597 480471353 706233574 351973334 105318731 418660489 957084764 506075713 691695407 33244712 357973729 606336334 154894555 289346185 978129750 966619798 979134496 167938179 818355103 922181201 699160598 515271124 401211687 866265054 538538904 436544924 515095897 105598527 467544005 547504862 682598952 770695834 688668801 736028418 73219208 974274745 143782130 138305622 894775026 238115723 653217283 977670280 266495972 272556449 282042084 739558189 506660959 417926065 52523911 328630846 823177319 843642135 934768421 216452246 11171719 210949199 129642680 936705141 543996234 590362492 548298110 783618048 137856451 780637925 285900668 186598846 375157254 119566194 372169209 709072668 24115372 880589107 377566718 328261355 438152276 226770905 304544989 356318173 861316636 622996795 363829415 852468491 580793388 286659539 206403764 480846450 607451691 182869823 384676895 384282993 251230664 755438784 763840072 695799116 835197746 316059070 456694608 726626732 956228000 866053698 421645984 65482013 652939211 554695546 152458594 262039951 400163951 742744632 860745990 822554838 693188814 619434356 503992767 994779946 624157484 304882374 989139204 359515048 148136788 824121068 638179343 239139022 878415633 342336074 594716257 543017219 337287350 771535205 904616508 80097549 238410647 651448167 775179560 105757336 886326926 786834079 395802222 703457462 424372855 875699454 759501216 504619610 874147508 294229146 77583 729103580 927210409 508365870 673326163 273075320 888857921 993583512 186694856 987438798 426124647 385813594 813665803 694948196 822149262 403439131 438653568 426692127 993290282 241706787 444444111 764539342 23779125 917879010 519463779 118434463 188092587 786961001 941290 116508328 203224078 790089967 743426264 4699231 722185186 813413965 289568483 351514914 794274866 333749123 845654152 617377713 437503241 716137777 727674245 841694895 924983546 162152478 901061725 83673892 749432217 3779509 672334039 528184573 477034496 146073219 370293887 175845771 897745739 312358587 201272612 461523456 851165980 977164466 663963480 409606645 58983960 687459171 130029300 80404967 613921895 303823595 125426065 586930613 658367032 702079246 583945999 631648548 210587707 170564529 193741842 758128731 250083365 999992669 76287616 704536679 502880559 656399811 229457412 535535032 310959768 891869747 303508110 641241250 261752350 844306467 742262481 729149918 877667977 913080750 709626052 731711750 398244897 734979602 987647522 12140828 199249714 857723441 987927274 557622019 804558991 916641553 195543007 273154053 674652172 814578780 88971528 667358795 939596035 178094817 904266801 409764712 280813776 426962193 478611305 786629839 892822357 501985154 343692162 948265048 722715511 62461808 222531221 730105535 640724383 240385847 682006651 555922981 932166201 6077146 838341972 862565005 940143672 631890559 833827844 190381152 380833168 658604273 296536753 205938922 796043707 274306077 555174215 557326042 297072693 951422357 69435892 632779974 385444608 226751760 715863980 995898789 270766369 271951592 301790886 463092563 933111585 559846042 392612573 143021840 642116492 785844042 815123600 817068033 855786869 948220988 322969282 260778926 72747249 36212060 631650234 685169282 892596631 363898295 955423620 963987023 554978567 3316736 998338671 324451015 866260320 845594380 683136398 511114756 855353799 346240086 382434615 127298305 172941543 514573436 803912070 526734366 597692780 774361024 756148955 920663968 311236743 226700423 329306712 372888622 557241965 595252189 224244836 453897557 409560792 687524848 466279722 316576773 847804292 204823185 80514331 120962835 276939955 295024054 783704424 507658165 633404330 484099578 66091656 549143561 567963442 977028380 373145272 964085646 374477335 299885180 883341430 392339880 375134124 220441505 224705798 708041248 406450246 667882165 869936365 621167010 644705725 208309511 786579576 394491454 215035374 336212360 390938166 836865512 260435771 419394895 688718714 911372024 355228937 620286997 803168986 306513067 409487424 560232634 124952243 548454816 740198863 280106942 749757346 663793243 246628134 137010120 162642700 578632133 605017787 186587683 728017815 14719402 505334918 592981308 654701487 777874746 598702212 853920549 298683906 761964424 26146103 432080405 960054788 184091662 627426340 413114086 947437164 757920551 647167572 913319318 545395637 19431060 441979091 442996166 476233374 538825208 546422069 461599550 966887594 778270556 697155084 419715175 331609249 626116523 70884211 177946319 221189901 838715191 128810886 364939689 99326654 296922162 986389735 451965002 404042055 889680694 586470715 926506157 854299006 430524862 955809707 515401200 45448704 355142826 722093924 906499285 738255786 317201599 595768855 819987522 26213409 725565733 73507449 326177729 757475915 74824679 175989444 175480833 446100180 814790263 573580085 350985555 257749675 572291111 730643084 124907566 668945794 165169840 91705999 855300011 369541713 828755631 661473927 516753417 460015571 882219043 495703488 239098154 882371847 908857073 35622926 381100821 83044272 179152736 239330371 248811122 321628886 598968989 797115578 514160913 107985219 46022968 998785999 350933091 85736455 940397478 377591397 131613183 899688693 870702269 259734622 290149407 352733987 457453114 773018406 21693984 632542574 58531646 996774441 909346054 243290356 246698189 211076953 495801333 10053528 21121102 120941481 46415033 187828353 568238606 965855636 75800639 509145243 478073277 655178134 601518874 916993812 164726511 179970738 846754303 999695328 54647196 26807019 406228041 35817014 85748384 42881994 795086453 617564946 752481852 574364382 331363495 800519601 573145235 791132728 208523556 177315351 781627438 412842731 728363222 839013260 250470008 935907730 615715787 11284250 393113155 256378570 584652726 796794385 175141442 810341811 514217581 604681860 185504653 407825011 243198057 292204490 144117280 738924723 290923337 895922941 565969243 544639520 589759567 464722814 116270211 732528363 731254497 779054447 838414656 954968650 601707785 370368055 279363101 495895285 613697526 135762178 948681996 641239465 132412537 398183743 2971615 121700264 229812105 666581280 291306704 684817207 789802687 629610013 989766906 405105183 762868955 937665905 389063389 797633070 680059965 324909724 660761822 859726259 675266924 656052191 871515588 936090628 929890195 456058051 115553084 856439803 361207551 867548818 389323351 677828213 279867298 422680796 837223943 443794642 246677395 361055732 740786597 625272184 82015628 359112049 913206126 733356112 743578475 462457517 742554881 463368519 897990833 450298697 960728547 458457807 270802182 367211943 740691451 333442651 606515379 382592879 200664598 973525222 465551142 987178507 784891492 514213229 145013618 925044010 73262841 227132272 378601164 695522625 858235469 655550837 19779855 769356805 102639548 723783045 819603257 526137074 373297159 63363502 505035244 546067399 654451666 601414271 703357422 642569992 867832868 502977422 586879145 124634747 736564457 954708982 238064811 574155179 991522675 423703249 310662183 139100264 609762037 280551363 479271283 853845829 105080071 859567471 224416648 798192153 656563237 737915391 301123205 112243327 940545584 328002464 889027117 286403670 248428267 325700867 67020900 448835649 92691071 424059870 943187893 923994663 550473719 448763753 832525775 558559156 460737989 951079138 931557891 223120599 712377403 575514121 227039176 243046978 89741843 491471268 524245816 233983981 203483368 67464188 862172048 528606100 506745275 257043295 308654516 755122996 410557294 344492188 732391592 452946322 120669004 702801290 870957592 550447796 534951295 54901121 853878993 444991589 625543065 55813086 4180805 896123061 115766540 722293892 628272652 382742135 713063346 600413270 668276830 291733954 298351173 417220542 289316505 453237361 524862696 336511273 78154433 558180003 544736156 504390537 510528763 952927547 684063948 873992402 204006929 105788001 6537154 913989757 887130097 224538623 783958831 639746055 274415150 501429316 291301799 740242291 817182333 112140325 474640930 532683716 562050874 303408087 547863165 56216452 188158945 611714390 468372471 531422017 458546580 599923426 655286708 316593162 353496476 860586365 129057598 179379190 106307040 33977710 306023166 193094301 540238703 422302912 39791815 440528797 428403453 614347716 290273868 789160726 249144157 190538122 967445413 871028270 424536076 590528108 286800335 718220175 580767142 752274564 808044840 490005988 571461742 774998065 779340279 9323103 109754059 108714134 882470114 377571126 910561733 876381723 757575029 119897633 957948300 429977322 92774050 138689758 263550450 96073075 731700540 288761774 70878444 62620392 108839546 147399637 221027092 273498050 628900475 758922269 438332970 303616570 942924988 148073300 535634830 575274705 723227811 514250953 170473672 72465096 733238776 643440339 716666369 716083369 394645350 963783498 350060167 84565180 442668287 500854284 850757453 750190483 674150069 470790522 918770024 54914687 901546210 857588984 318977683 559398936 477947585 926269808 417801132 724796600 131931378 952820175 139992885 920951040 938956282 709339015 288195540 76594259 860486849 618770188 639734483 977420118 742238994 974742615 10844832 239569015 989881886 382258534 649073998 7179874 924743417 202899642 538825491 121510029 818308892 872985047 935963336 331663277 522291937 472463303 144749676 753583167 448935946 221934488 951528353 42866945 35540539 633952985 164399661 113309557 703430523 216138273 478465659 227025509 279491255 84551048 991033880 558843993 155219007 260452140 249447990 60894243 170680903 256347566 309607980 43523924 533352808 550721714 155871219 457451716 737964316 405152611 375147179 990449422 340448325 48334060 247203092 384401681 165580198 357792000 702327317 497746544 410057320 953988178 392819513 437657107 571127447 535645982 927705389 183302820 239754147 121207711 603856452 778122515 123438304 464623766 22481651 752705299 326627334 635336650 281346645 772329882 177100721 717544578 528011431 272570213 680731106 72350221 346879949 832096113 86743164 881451066 520124876 621971843 461773768 745449440 758277966 568699041 60272369 452142936 862118945 634729367 559647369 429402366 583161272 114972020 544852227 75499955 200576424 828881418 646829366 584052062 415816748 432834161 421348576 781810534 152678050 828167044 263206689 708546873 636224012 798925410 643858684 973718729 418798480 715011823 623146457 234915594 772722937 729954896 99874822 928484982 8729907 467420531 136249137 248136073 182139090 246083461 535921392 180521796 122166412 368306297 428280121 424131502 699332538 966538632 915036906 868136014 630784220 733970859 541910594 87229107 8707090 439858211 533927270 847968492 884813731 586311922 740393693 285871632 240789626 738049375 55547412 626686136 737830564 776110198 231324124 725119872 832077779 932192646 534272231 197221257 931145694 888160417 505711694 456593658 382617407 678847775 88351246 967775610 888796563 601643035 787260806 590405304 109048350 878847220 649014778 530645220 633365572 387271630 441348371 931507507 121998353 445027343 992315741 463333982 290337458 388724962 736163528 572151587 321383162 847909303 762360104 552905411 205152222 288289985 685884597 734248835 266879225 603028342 716729996 172903723 115057929 413671187 777803051 629376906 119006832 456020758 667418361 980860655 480373172 823515074 324433084 538958513 207541247 288730270 836204064 972736937 630271391 914534646 477231671 241473715 72024199 169818201 224315892 656768305 159434445 240199961 126223023 931106183 797440810 377938638 278135460 343901088 42667901 719890643 65940339 140030312 947482440 914003144 310082210 738784079 887256113 51106062 767695894 774981836 285462147 772644686 27845790 499508440 593711018 605789427 825817704 75017839 215908026 674680747 108958090 264611603 702481129 556521 878256250 189805384 594549265 392992614 861714582 939941145 545406255 749652892 273788574 221227666 971119335 229015626 656378165 897001027 596707837 565231603 474511203 618947524 117548509 150958686 537338645 689750059 866915092 216344343 993138076 700414615 181355476 266664941 343435306 30346921 928830068 34276210 909528152 176030982 835948526 109093246 436198051 675732438 156834912 922009005 125697258 593947464 867681163 789665244 602097906 773004812 956932439 799943344 700212450 629507543 663257165 727034895 438908359 56043491 911105051 633719204 360083985 600847724 168997396 341894495 729890836 599850036 233443757 137171443 713315977 775581951 828358914 725747543 633806090 452140056 861153614 263389510 627500697 720537035 393693046 261184446 524427801 425300713 328728191 788151173 584785108 942523719 42430484 886154911 516317427 616870462 319020289 22146265 842232841 821094189 334209978 394625602 608178057 654488050 506538197 740858796 909930315 979460981 370467723 176287536 182566411 528434718 311309372 552911527 194554858 808598618 462188776 163741233 24364267 490703641 279563190 935208626 609076599 381968467 853850992 71911504 380148954 557120894 425151493 119879927 624523203 116768794 376602887 466149077 194988744 683780134 326905387 823902942 635894496 206142631 873673163 514193737 405796839 967533608 865111399 844612624 691789597 765435701 833874463 443217780 7779239 355767007 214829883 684044408 891337997 524130107 332889764 163628385 885814714 938309091 288381800 422027324 292170112 345815155 728479801 717828440 39585809 548062989 911482863 932301767 796937607 980567254 894400002 384658914 764383453 647962230 19361040 558531010 150173811 431516316 872175965 949485512 267548302 244745848 52782414 940440853 469589973 297525823 740857325 500066834 509654997 327449515 856003432 488402154 8544126 483070072 634226066 579009547 668443045 573232360 314701409 135819433 835606912 297079360 106606702 534428475 656368429 194475849 815361912 237035516 958017067 279734992 808386785 385616747 584198110 25262118 815120943 250659531 677998607 357137312 451855757 144759972 436715370 508779288 666454599 386058560 853069311 335341674 383071057 49192239 376615362 21523960 141833153 417866691 999323915 594007847 118524241 650365845 158679319 235280608 412248798 586197758 566890629 270443024 546423531 492698783 323097561 20882472 56669727 808235482 459986428 579769757 862155202 540324182 82689722 397057129 284202564 566610303 193147203 223348872 274884023 552478979 806101162 992210044 219275856 412181846 259246185 650186698 708498154 442039087 272933595 912045435 853742466 62797065 667866049 733592220 498326460 493463971 374817982 412743358 162500445 501441664 287228379 393098358 627408079 429118056 710760451 619124702 146198432 904724453 636090248 114396434 796584195 404552647 328653468 22541492 177739853 738484129 722041305 825882729 139158393 11475017 485792442 852699994 566163365 739723356 48685600 165019316 968405395 266559671 458863309 126556712 181650473 709468927 704465388 435833452 471990513 236687386 489249159 967432119 442976921 694438580 577902352 225367625 742817652 520394683 943210457 922167009 382235640 32615652 529166747 508580677 442082110 326229284 764987123 555804350 678969734 748376887 922756576 533718169 905274544 436465180 622332487 934129831 562931395 325789590 484721775 747568061 130630250 583865005 833071493 296148533 509856625 239044139 374864410 691106924 783738189 403413792 728615584 205637442 674660754 878154591 18865648 928782493 781671546 88077822 355894214 48797670 909623141 364610522 937571139 286613130 274566995 721605648 178773355 516340346 720793452 103601797 576033701 247567531 123722104 753681504 326707774 125937047 322075239 530729099 630486246 840812987 955079371 757647925 252035889 966607895 185676633 996844370 580257559 201752241 485519724 861411609 836307828 142206738 963073410 915421829 479599753 297599175 660607421 919715029 853131897 443532769 20912226 804835341 889396685 290380661 343117405 564709747 315436016 803400221 267435452 966103570 834397108 223147126 629975600 920097082 395596236 159092640 695849871 83803390 680654160 727224769 627940436 987117236 158274108 658247298 807107613 349388665 271139312 622537104 605987884 796176555 304515505 548523804 379191784 304855661 359085863 470341724 842502489 947048486 728267485 231497224 225349551 86713602 908113605 145961181 695372219 430748783 215533233 162524190 261634675 679773346 624133851 411638798 964817779 691389712 717926494 704614519 831094647 209638645 215433146 896016678 587154658 204065744 461555540 472832620 689049147 166598117 840563699 266053535 804633770 796084922 769214788 915397527 649515647 998980506 243451480 377818929 538022316 207601173 57771553 393239503 774458950 529986174 238701048 767740375 48324872 523270252 702831642 708152112 311747535 304319801 324637734 172830152 883047455 432264326 564308897 324109328 789812636 986012341 227152498 385116030 284401810 148957038 935159654 435588362 67571823 308759578 835215533 301759409 5763651 88068715 678906459 264541430 208892743 727278802 380563688 646916444 216000339 410119432 236252592 883575021 342290789 857932934 704141684 506110902 897486881 715986700 650869976 31951944 84419660 15904542 645922019 918709817 911844176 301651074 512188801 699823777 853742012 692528835 502493188 892203677 245278657 873844145 540143007 357374416 807820214 125187039 606229482 939277021 655758996 614293284 659104609 282201582 322323578 597892891 405217253 360665904 51914538 484858786 204269881 246962517 377653898 470711646 755737478 377181712 402000677 892960310 74323415 786514588 713427112 701786580 847500446 144103478 491033701 931050024 733346349 556355230 375797203 251483108 256173886 124613275 709517579 337880832 795341676 321547380 773395277 176727351 249939384 483069047 657044857 93096585 457712900 190095221 572789911 455855032 863313051 338159428 740294223 79441099 362806951 271105340 984914289 358341005 21620922 778981563 208550511 111583758 41772102 539516833 93940702 386519329 667162917 388570324 218109689 745657565 488209425 752097981 532395038 111907613 18587437 850701258 722139470 108255232 602790522 280846058 391719601 176998505 895547491 197713940 9060624 955009151 636597810 669942976 154713178 635120686 293768344 799722604 884851743 23037861 428937769 70107416 298667032 555712471 326717405 543887818 241002141 964825338 590246289 183890188 107353901 393941770 259501188 985047913 80956138 985055303 179070938 974550515 160468762 776011186 175421213 534051008 537665447 61533076 336523958 226427240 50192288 930340856 672707704 776003977 614936502 234468140 370219542 881336643 375528128 194809412 463868840 815454141 835376183 956716439 975879211 491969950 496920251 406623552 436699645 526824852 450801292 760297374 877385573 167908561 393756177 423621076 814941449 763157384 957723733 997956682 629820533 279564149 678502277 828218154 469392539 140270675 718381939 470998756 176917582 22401635 753970198 880542890 175003846 967642347 645682696 752754933 204825119 403844789 215043334 763815422 510159833 298610316 313219700 652260421 149957977 832312258 642268630 89987854 35784807 602527405 640652632 95698655 850113454 120912677 224280136 134451716 58485056 847080200 900690326 210961163 642402063 689006263 816233050 390899528 64328053 208362390 808365646 885350226 510585773 609355407 125511760 330619780 522120791 540701840 979072226 554039933 888048120 284690696 960615594 419829665 817426808 566521966 196095218 662898581 740964514 352594106 189564969 515814598 552778919 979107818 308575840 484609507 402329755 294001791 491700173 907599455 834002935 147071997 710742347 244538096 363814165 682878319 322919129 856192019 218032567 548619744 313457175 78275717 661798785 814812386 589798092 929630667 257567354 180316939 894410082 909594795 187809679 818666612 710570344 230123441 768689424 857227065 718425103 815934891 224064305 783286779 545118382 715119661 245803147 649120865 435953471 493811214 445746328 604769170 230537439 527606761 578633274 543200444 345533521 86641310 609381428 727440273 221193340 900843470 910229936 631030469 201246441 577934946 139423415 64056977 118209606 57784580 565038780 785713971 675049701 322373284 377436946 780875628 732262717 607143668 184583537 377670912 87677032 575440621 816565365 931218233 142013604 408625992 200157727 788961637 879850451 528476422 235144786 48580948 648278522 20300777 21432151 500809690 309106629 66804984 790592601 66484051 734842626 889552127 994440682 847778330 165527329 945561868 280892541 180183824 73093051 467474164 121886441 278645276 413441288 618331084 518550764 217783973 909796455 819721328 371159974 923969050 994085082 445731839 984211482 843025002 980907399 138737756 111656880 172698764 212147768 735440047 14568630 518533881 143733724 394739170 186831066 631185965 3213572 171726629 784884658 928739113 5912679 601167467 523196724 68421620 395686238 57378027 529309246 217868309 550098024 155275167 613009167 152629531 437364135 271375304 666712524 445140758 491079010 271561064 837608700 984335131 757769857 636063686 98637324 510762435 482342164 273338350 755149773 262405036 76454605 77431598 863210737 450141687 926872448 344065947 301004945 387662536 629817258 565423754 75981994 641887690 103658216 599240471 916999323 756933288 861654139 674049185 705784232 97608085 728066507 411598156 954005370 913721797 637064417 965735550 533296797 469095410 406268651 683492706 445662465 338323672 222498491 629356904 478810234 708679608 539061577 284859587 574269248 728581337 109311533 814382313 428188272 950820866 29204517 512694551 474371208 732451074 430997 67977931 533182959 386182185 510029058 1690184 659827563 12827852 465022358 463353109 297979048 241971140 171931552 460477566 136589496 791071215 105925393 906017298 367603342 5203118 796051967 290709027 129010050 20545126 225338661 756389961 775053776 229859071 378765921 403795935 899246360 830765160 520749878 810451588 926153952 123686673 772793160 510332572 241042189 223521903 956877026 598164429 163959918 223634811 520679283 282342786 694523185 327711027 248327180 811505515 654510956 437629720 222369252 82132987 468839317 846282671 575967956 53811433 296552202 842754816 658437596 510270384 627530379 355753754 555627932 8206862 173468859 94807693 21237980 799713929 526812322 185973998 923959044 405455077 350363181 435256150 97104036 339630255 13726893 296568036 251412974 358081974 664406868 202400054 440946487 799745164 736215995 252545780 250212218 712597257 663606879 174423622 510782676 120687304 765045535 939674456 822461705 764618665 893156288 989795037 38877694 562157645 986587753 649661577 73112637 976053405 192834087 799473046 318091124 861373508 144925034 897344320 931242742 959308592 190449798 578640201 419167288 965106197 957020212 925646966 604096341 595755754 68762126 711308559 47420811 215691625 502384406 315347811 674548156 90635155 51808816 329744450 169921774 143415338 266149027 596320641 34182859 136249142 809200283 770773626 520266274 958659201 938093482 824781961 966461284 757827611 481892163 805376400 331069735 434931414 536680254 118725235 667330727 746680010 308687959 303120285 251525696 954086355 7344303 812336506 884751861 837420046 868791881 595230971 292192237 682634848 316330382 16715285 639406320 477525231 997722570 599495746 69785326 67160998 618972588 607433470 453141368 163754678 656129994 626124875 677747269 4598031 250449691 591062318 425848751 268383467 937481083 368843823 539103539 819646020 499624490 144191965 61902325 947444057 325450317 201299272 640297785 141749037 71894380 513563269 859901163 901796360 733430770 143584558 409746456 835002868 176673201 404080351 162534259 612105025 397569627 784660922 766600657 556397825 249634826 934869732 29029037 896605069 209970617 908700422 937319589 707677950 163729864 573514956 894234619 526326196 362778236 811104105 48530196 559922899 121368700 97887506 860886780 410400449 205573461 506506110 599627233 179328426 767233016 212342381 636139412 261473788 89773367 520787998 509658123 756435179 991000651 66882006 780278242 718757614 861104977 233811552 476451541 61291584 528292296 760960648 947232327 330146656 772071188 266598815 157877694 618650001 951754494 986873850 272924004 920203611 879787571 219287411 902923400 530889992 783660736 281256934 253041691 31366440 482693788 921501621 948016436 895862029 193290271 887768645 375885708 612352848 992018051 749470847 366709763 302635082 99070058 894147920 530141465 336225436 138298967 100739625 395586421 825403303 886217011 355033471 681301090 447594005 260162762 533754700 781840461 464602190 811769420 349395340 610291528 175236868 301162188 620728513 106513290 235569064 187240388 604402288 915188205 693083378 251949967 934586274 541440111 299395933 933201390 821087588 64166065 595311528 408676996 239484231 666667131 184172886 885589850 223057888 514321974 363271983 116217180 294543177 214066032 874222013 288648921 67099039 480281948 818880464 447830535 640390018 867362639 922735866 481617276 660137112 474174788 459786772 412157622 374730249 118367321 431161271 222495893 770532612 325908816 393802436 286774747 939124537 392202511 594249949 355904435 208362334 240737568 317427945 80155687 436305323 188524082 387769236 289174185 394883165 586131094 53497804 905120907 561077814 844409027 16453957 653458822 525888251 485934034 531469558 984127031 591219701 667412482 361429914 357587613 175375985 708000053 549137456 452780189 191811648 52617074 249898108 243355262 718564920 238452065 34759044 973880686 386909360 512046802 983016979 934699515 511053320 788636470 737422649 692908186 677666591 766863396 983667400 933692451 311342043 333840854 42049497 578350674 335107493 348349353 447760710 876102728 686461930 208241313 573523501 365280009 929236123 219959266 519999091 398625276 272382638 878362424 114004798 481565550 724934810 893557136 487265146 618252047 844345567 842075517 376177750 817783923 809632380 389708724 744377796 787346834 430393207 762748816 443656956 696383816 620232537 211760526 879548153 691618774 442200495 921936850 523111674 291998047 597478026 346430625 118146819 836657260 418612480 305699045 722928730 880705641 290916265 977924268 301903882 85120037 792017186 1769385 13074787 768840278 517536397 756312498 818390648 804681235 47548943 31366464 869744799 991712088 122652497 598522354 213812981 347343749 67315712 179273994 22524120 323077087 781296718 171469294 305880171 474893326 831081838 795618984 552734997 96137373 282017819 309022823 339365890 207310718 527428370 333666812 204786336 686585987 497252755 883774046 864938788 146717158 753910244 653680934 469578499 864750274 624378318 89441556 71279993 494853527 671593758 382329992 244191749 650708170 618693669 310828041 658736875 908552994 803388473 194390210 793841584 379255885 62284338 383170304 186375074 738426201 583452909 336970933 486817358 830110523 572281293 391300600 254557192 810281803 777354549 561878403 265764454 105155526 61487375 794779956 938516165 317096011 375300936 344028812 991626947 321471071 479429201 358146355 959455939 953940457 218208672 909221234 489818220 418386358 127154733 23758007 885130538 158030326 158997237 524589589 813369516 625764029 127758203 324753601 114287972 328724099 419902018 812503702 733999370 925511332 533691732 754626706 323781914 713667553 341070526 149248855 470272337 597923038 25872145 784058795 398197811 814206114 782333923 194564344 552942472 473256218 43874380 702542284 687996123 543128981 643665258 501016666 669099514 463665481 67504861 320732408 843202937 63184333 916578635 913299615 675661615 669918109 632355549 43415919 693849270 47404186 40504768 423870760 364748271 494918791 505552038 493021617 872799612 147198349 242125634 497783700 548672325 69275831 571776720 565968512 494009076 876829303 208700554 985986502 302888056 446277407 903363124 860767965 944600710 521864553 288873105 235905503 817142547 267399408 85187051 594540041 349948891 100080821 390615695 560761407 270432478 140580251 937651022 562133893 85947613 715718378 121120766 880138631 640405985 27456720 891637751 766119186 261287861 533855451 876396695 534123161 640147047 550677632 692662206 719829681 869635275 217131928 8667731 747624085 743309048 204714717 649202365 265084578 934940873 454126194 885747050 789370588 374817884 219225688 715586379 303545704 983125143 936233722 262086230 421197584 794563998 53250978 420446211 161325506 525500254 834467073 921513424 903270161 791973894 91823531 190818749 137053362 300248712 974245016 325025489 917651201 175641373 135533989 579448211 961433978 413815742 168417809 18438289 670456128 515178155 181090048 312640733 417244569 368923368 783430140 609813642 426813551 855510203 713129839 182969652 358173393 272044592 766196521 745754741 327923056 761363349 784788704 575795825 52746530 177806846 43641515 515042891 390096739 1211842 42776455 558117037 312635599 70764796 524873170 391764549 957191593 884026379 615345107 929733698 789241432 668576274 84628016 617606363 892283876 245052281 876692597 540046280 345837693