Informatica Online Judge

  아프리카 화폐 [0648 / 0288]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 14   Total Tried : 18


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

하림이가 아프리카에 어떤 나라에 여행을 갔다.

나라는 물가와 우리나라와 다르기 때문에 화폐또한 우리나라와 다르다.

하림이가 그 나라에서 자판기에서 코코팜을 사먹는데 동전을 넣는다.

동전을 넣는 순서가 다르면 다른 방법으로 취급한다.

값을 지불할 수 있는 모든 경우의 수를 100만으로 나눈 나머지를 구하여라.

Input

빵(n)의 값과 그 나라의 화폐의 개수(m)와 단위(a1, a2, a3...)를 입력받는다.(n<=100000000,m<=50,ai<100000000)

Output

지불할 수 있는 모든 경우의 수를 1,000,000으로 나눈 나머지를 출력한다.
단, 빵의 값을 지불할 수 없는 경우 -1 출력

IO Example

입력
6 2
1 4

출력
4

설명)
1+1+1+1+1+1
1+1+4
1+4+1
4+1+1

출제 : 김하림(GSHS-29th, 2012알고리즘수행평가)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]