준혁이는 장난감 공장의 공장장이다.

이번에 새로 나온 장난감을 설계하기 위해 준혁이는 총 M개의 부품을 주문하려 한다.

부품이 남도록 부품을 더 주문하는 것은 상관없다. 하지만 부품이 없어서 못만드는 경우는 없게 하려 한다.

그러나 부품 공장에서는 단순히 부품을 하나씩 팔지는 않는다. 구체적으로 총 N개의 팩이 있어, i번째 팩에서는 총 si종류의 부품(p1,p2,...번)을 팔며, 오직 팩 단위로만 물건을 내놓는다.

준혁이는 부자다. 그렇기에 각 팩의 가격은 궁금하지도 않다. 그러나 수학에 관심이 많은 준혁이는 모든 종류의 부품이 적어도 하나씩 있을 팩 조합의 개수는 궁금하다.

모든 부품이 적어도 하나씩 있을 팩 조합의 개수를 준혁이에게 대신 구해서 알려주자. 그러면 준혁이는 감동해 여러분에게 용돈을 줄지도 모른다.

부품 설계 timer 2초 memory 1024MB

부품 설계 2초 1024MB