Задача J. Хейтеры единицы ≡

Условие

Настя обожает математику, а сильнее всего Настя любит натуральное число n. Еще у Насти есть q друзей, i-й друг любит натуральное число x_i (причем Настя и ее друзья ненавидят число 1, поэтому n, x ≥ 2).

Настя очень добрый человек, поэтому для i-го друга Настя найдет сумму x_i + x_i² + ...x_iⁿ. Также Настя очень ленивый математик, поэтому каждому другу она будет говорить остаток от деления суммы на 10⁹ + 7.

Помогите Насте! Сообщите для каждого друга его остаток от деления суммы!

Формат входных данных

В первой строке вводятся натуральные числа n и q — любимое число Насти и количество друзей Насти соответственно (2 ≤ n ≤ 10¹⁸, 1 ≤ q ≤ 10⁵).

Во второй строке вводится q натуральных чисел, i-е число равно x_i — любимое число i-го друга (2 ≤ x_i ≤ 10¹⁸).

Формат выходных данных

Выведите q чисел, где i-е число показывает остаток от деления суммы i-го друга на 10⁹ + 7.

Обратите внимание, что каждое из q чисел лежит на промежутке от 0 до 10⁹ + 6.

Примеры тестов

3 4
2 3 5 235235

14 39 155 816225021