Маленький мальчик Максим недавно узнал, что такое треугольник Паскаля. И ему так понравился этот треугольник, что он стал модифицировать его различными способами. В результате у него получилась следующая структура:

                                      1

                               1       1       1

                       1       2       3       2       1

               1       3       6       7       6       3       1

        1       4       10      16      19      16      10      4       1

 

     Формально, каждый элемент этого треугольника — это сумма трех элементов предыдущей строки, стоящих прямо над ним, левее на одну позицию и правее на одну позицию, или Z[i, j] = Z[i–1, j–2] + Z[i–1, j–1] + Z[i–1, j], где i – номер строки, а j – номер позиции в строке (самая левая единица в каждой строке имеет номер позиции, равный 1). Элементы в отсутствующих позициях принимаются равными нулю.

     Больше всего Максима заинтересовали элементы центрального столбца построенного треугольника. Но так как Максим еще маленький, то ему сложно складывать большие числа, кроме того максимальное число, о котором он знает — это 10⁹. Поэтому он просит Вас помочь ему вычислить значение Z[N,N] по модулю 10⁹.

Единственная строка входных данных содержит одно натуральное число N (1 ≤ N ≤ 10⁴).

Выведите одно натуральное число — значение Z[N,N] по модулю 10⁹.

Примеры

Входные данные	Выходные данные
1	1
3	3
5	19