오백나한도
시간 제한2초메모리 제한1024 MB
n명의 보폭이 주어질 때 이동거리 총합이 K가 되는 음이 아닌 걸음 횟수를 찾거나 불가능을 판별한다.
문제
국보 제 1883호로 지정된 '고려 오백나한도'에서는 500명의 깨달음을 얻은 나한들의 모습을 보여주고 있다. 역사에 관심이 깊은 한별이는 이 그림이 마음에 들었는지 자신의 방에 걸어두고, 잠을 잤다. 그날 밤, 한별이는 기묘한 꿈을 꾸었다. 오백명의 나한들을 만나게 된 것이다! 나한들과 즐거운 시간을 지내던 한별이는 나한들의 발걸음을 주시하다가 문득 특이한 성질을 발견하였다. 나한들의 보폭은 자연수이며 각 나한마다 항상 일정하지만, 서로 다른 두 나한의 경우에는 다를 수도 있다는 것이다.
프로그래머로서도 호기심이 왕성한 한별이는 다음과 같은 궁금증이 생겼다:
“나한들이 걸은 이동거리의 총합이 가 되도록 하는 방법이 있을까?”
한별이의 궁금증을 해소하기 위해, 나한들이 걷는 방법이 존재하는지 판별하고, 존재한다면 그 실례를 찾아주자!
입력
첫째 줄에 가 주어진다. 이는 각각 나한들의 수와, 이동거리의 총합을 의미한다. 이후 두 번째 줄부터 번째 줄까지, 번째 줄에는 번째 나한의 보폭을 나타내는 하나의 정수 가 입력된다.
출력
만약 나한들이 어떻게 걸어도 이동거리의 총합이 가 될 수 없다면, 을 출력한다. 그렇지 않다면, 총 개의 음이 아닌 정수를 출력한다. 이는 각각 나한들이 걸은 횟수를 의미하며, 문제의 조건을 만족해야 한다.