飽き性くんと工場

解説

全工程数の総和を$M$とします。

タスクを区別しない時、選び方は$M!$通りあります。 ただし、同一タスク内の工程は、配置問わず並び方が一意に制限されるため、表現幅は$a_i!$ずつ失われてしまいます。

なので、$\frac{M!}{\prod a_i!}$mod$10^6+3$が答えとなります。

この数式を一見すると、$O(\sum_{i=1}^{N}a_i)$もしくは最悪$O(10^{11})$の計算量が必要だと、怯えられるかもしれません。

ただ、modに注目すると、$M$が$10^6+3$以上のときは、答えは常に$0$になることが分かります。

これでこの問題を解くことができました。