군대 모집

로버트 바라테온은 타가리엔과의 전쟁을 피할 수 없다는 것을 안다. 지금은 겨울이라 타가리엔 쪽은 여름이 시작되기 전까지 공격하지 않는다. 여름은 1년 뒤, 즉 366일 뒤에 온다. 그리 긴 시간은 아니다. 그래서 로버트는 이 기간 안에 군대를 꾸리려 한다.

로버트에게는 $n$명의 기사가 있고, $i$번 기사에게는 $a_i$명의 병사가 딸려 있다. 로버트는 기사들에게 병사를 더 모으라고 명령했다. 매일 저녁 로버트에게는 다음 형식의 보고가 도착한다. $l$번부터 $r$번까지의 기사들이 병사를 한 명씩 더 찾았다.

로버트는 언제든지 $l$번부터 $r$번까지의 기사들이 거느린 병사 무리를 살펴볼 수 있다. 그 정보로 $r - l + 1$개 무리 각각에서 총사령관을 뽑는 방법의 수를 셀 수 있다. 무리의 병사는 모두 똑같이 총사령관이 될 수 있다. 두 방법은 총사령관 중 적어도 하나가 다르면 다른 방법으로 본다. 값이 꽤 커질 수 있으므로 로버트는 1000003으로 나눈 나머지만 알고 싶어 한다.

칠왕국의 왕은 수학에 능하지 않아서 당신에게 이 문제를 풀어 달라고 부탁했다.

첫째 줄에 기사의 수 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에는 $i$번 기사가 처음 거느린 병사의 수 $a_i$ ($1 \le a_i \le 10^9$)가 $n$개 주어진다.

셋째 줄에는 쿼리의 수 $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$이면 $l$번부터 $r$번까지 기사들의 병사 무리에서 총사령관을 뽑는 방법의 수를 구한다.

병사 증가 보고는 하루에 한 번 이하로 오며, 즉 $a = 0$ 쿼리는 최대 366번이다.

각 $a = 1$ 쿼리마다 답을 한 줄에 출력한다. 답은 1000003으로 나눈 나머지다.