У Джона Доу есть n отрезков на прямой. Отрезок (a, b) (a < b) — это множество точек x, таких, что a < x < b. Говорят, что отрезки (a1, b1) и (a2, b2) пересекаются, если существует такая точка c, что a1 < c < b1 и a2 < c < b2.
Джон хочет покрасить каждый отрезок в чёрный или белый цвет так, чтобы никакие два отрезка одного цвета не пересекались. Он хочет узнать, сколько существует различных способов покрасить отрезки таким образом.
Две покраски считаются различными, если существует отрезок, который в одной покраске покрашен в белый цвет, а в другой — в чёрный.
Пусть количество способов покрасить отрезки равно x. Выведите остаток от деления x на 106 + 3.