14731번 - 謎紛芥索紀 (Large)

문제

성민이는 이번 학기에 미적분학 과목을 수강하고 있다. 다항함수의 미분 단원 과제를 하던 도중 미분을 하기가 귀찮아진 성민이는 미분하려는 함수 f(x)가 주어지면, 미분 된 함수 f’(x)를 자동으로 구해주는 프로그램을 만들어서 계산을 줄일 생각을 하였다. 우리도 성민이가 원하는 프로그램을 한번 같이 만들어보도록 하자.

입력

첫째 줄에는 항의 개수 N(1 ≤ N ≤ 100000)이 주어진다.

둘째 줄부터 N개 줄에 걸쳐서 항의 계수 C(0 < C ≤ 100)와 항의 차수 K(0 ≤ K ≤ 10⁹)가 항의 차수와 관계 없이 무작위로 주어진다. 항의 차수가 같은 항은 2개 이상 존재하지 않는다

출력

f’(2)의 값을 10⁹+7로 나눈 나머지를 첫째 줄에 출력한다.

제한

힌트

f(x) = 3x³ + 2x² + x를 미분하면, f’(x) = 9x² + 4x + 1이 된다.

그래서 f’(2) = 9*2*2 + 4*2 + 1 = 45가 되고, f’(2)를 10⁹+7로 나눈 나머지는 45가 된다.