Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых квадратных клеточек, а второго разрезал на k уголков по три клеточки каждый. Теперь он интересуется вопросом: а сколько способов разместить эти уголки на полоске так, чтобы они не пересекались (то есть, чтобы ни одна клетка полосы не была покрыта более чем одним уголком). Петя не может отличить один уголок от другого, так что расстановки, отличающиеся только порядком уголков следует считать одинаковыми. Так как число способов может быть большим, а Петя добрый мальчик, ответ нужно вывести по модулю 109 + 7.
Два натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 109.
Выведите единственное число – ответ на задачу.
2 1
4
2 2
0
3 2
2
10 4
5820