飽き性くんと工場

問題文

林くんは長谷部工場の日雇いバイトを始めました。毎日のタスクは$N$種類与えられており、各タスクの操作は他タスクと完全に独立しています。

各タスクの工程の数は$a_i$で与えられます。

林くんは飽き性なので、一日通して過去と全く同じ順番で工程をこなすぐらいなら、もう辞めてしまいたいと思っています。

長谷部社長は林くんを何日間この工場に引き留めることが出来ますか? mod$10^6+3$で求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq a_i \lt 10^6+3$
• 入力はすべて整数