Ползунок - это шахматная фигура, которая может перемещаться на одну клетку влево или вправо.

В этой задаче используется цилиндрическая шахматная доска, левый край доски соединен с правым. Таким образом, находящийся на левом краю доски ползунок может сделать шаг влево и перейти на правый край доски, и наоборот.

Пусть $L(N,K)$ будет количеством способов расположить $K$ не атакующих друг друга ползунков на цилиндрической шахматной доске размером $N \times N$.

Например, $L(2,2)=4$ и $L(6,12)=4204761$.

Найдите $L(10^9,10^{15}) \bmod \left(10^7+19\right)^2$.