[소프티어] H-클린알파

제한시간 : C/C++/Java/Python(1초) | 메모리 제한 : 256MB

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

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

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

 

입력형식

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

입력은 다음 조건을 만족한다.
     1 ≤ P ≤ 108 인 정수
     1 ≤ N ≤ 106 인 정수
     1 ≤ Ai ≤ 108 인 정수

 

출력형식

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

 

입력예제

3 3
1 2 3

 

출력예제

18

 

import sys

p, n=map(int, input().split())
a=list(map(int, input().split()))
temp=0
for i in range(n):
        temp+=a[i]*p**(n-i-1)

result=temp%1000000007

print(result)