Набор в армию

Роберт Баратеон понимает, что войны с Таргариенами не избежать. Но сейчас зима, они не будут наступать, пока не начнется лето. Лето наступит через год, то есть через 366 дней --- не так уж и много. Поэтому Роберт хочет успеть собрать себе за это время армию.

У него есть $n$ рыцарей, у рыцаря с номером $i$ есть $a_i$ солдат в подчинении. Роберт отдал приказ своим рыцарям собирать больше солдат, и вечером каждого дня ему приходит донесение, которое имеет следующий вид: <<Рыцари с номерами с $l$ по $r$ нашли себе еще по одному солдату>>.

Также в любой момент времени Роберт может посмотреть на отряды солдат рыцарей с номерами с $l$ по $r$ и, исходя из этой информации, посчитать количество способов выбрать главнокомандующих у каждого из этих $r - l + 1$ отрядов солдат. Все солдаты в отрядах равноценно могут быть главнокомандующими, два способа считаются различными, если в них отличаются хотя бы два главнокомандующих. Число может получиться довольно большим, поэтому Роберт хочет знать только его остаток от деления на 1000003.

Король Семи Королевств не силен в математике, поэтому он попросил Вас помочь ему в решении этой задачи.

Первая строка входного файла содержит число $n$ ($1 \le n \le 10^5$) --- количество рыцарей у Роберта.

Вторая строка содержит $n$ целых чисел $a_i$ ($1 \le a_i \le 10^9$) --- начальное количество солдат у $i$-го рыцаря.

В третьей строке входного файла дано число $q$ ($1 \le q \le 10^5$) --- количество запросов. В следующих $q$ строках входного файла описаны запросы. Каждый запрос описывается тремя числами $a$, $l$, $r$ ($0 \le a \le 1, 1 \le l \le r \le n$).

$a = 0$ означает увеличение количества солдат у всех рыцарей с номерами с $l$ по $r$ включительно на один.

$a = 1$ означает запрос на подсчет количества способов выбрать главнокомандующих у отрядов рыцарей с номерами c $l$ по $r$ включительно.

Гарантируется, что донесенение об увеличении количества солдат приносили Роберту на чаще одного раза в день, то есть не более 366 раз.

На каждый запрос с $a = 1$ в выходной файл выведите ответ на запрос.