개발자 크루

남양연구소

남양연구소입니다.

Lv. 4

썸네일

H-클린알파

난이도
4 단계
참가자
0
제출
0
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 1초 256MB
C 1초 256MB
C++ 1초 256MB
Java 1초 256MB
Python 1초 256MB

나날이 심해지는 미세먼지로 인해 야외뿐만 아니라 집 안에서도 마음 놓을 수 없는 날이 계속되고 있다. 유해 물질이 창문 틈새로 새어 들어오거나, 외출 후 옷과 신발 등에 붙어 들어와 집 안이 오염될 수 있기 때문이다. 현대자동차그룹에서는 입주민들이 미세먼지 걱정없이 집 안을 깨끗하게 유지할 수 있도록 세대 내부에도 H 클린알파(H Cleanα)를 도입했다. 미세먼지 제거와 공기 정화는 물론, 바이러스와 세균까지 잡아주는 기술이다.



H 클린알파의 성능 테스트를 위해서 아래와 같은 조건을 가정한다.
1) 1초 간격으로 바이러스들이 집 안으로 침입한다
2) 집 안에서 바이러스는 1초당 P배씩 증가한다
3) N초 동안 죽는 바이러스는 없다

매초 집 안에 침입하는 바이러스의 숫자가 주어질 때, N초 후에는 총 몇 마리의 바이러스를 잡아야 할까?

제약조건

1 ≤ P ≤ 108 인 정수
1 ≤ N ≤ 106 인 정수
1 ≤ Ai ≤ 108 인 정수

입력형식

첫 번째 줄에 증가율 P, 총 시간 N(초)이 주어진다.
두 번째 줄에 매초 침입하는 바이러스의 숫자 Ai (1 ≤ i ≤ N)가 주어진다.

출력형식

최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하라.

입력예제1

3 3 1 2 3

출력예제1

18