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

Незнайка решил задать собственную последовательность, в которой каждый элемент задаётся формулой $$$a_i=(a_{i-1}+2*a_{i-2}+3*a_{i-3})\% mod$$$, где $$$a_1=1$$$, $$$a_2=1$$$, $$$a_3=2$$$, $$$mod=10^9+7$$$, а символ % обозначает взятие остатка от деления.

Незнайка сильно обрадовался собственной последовательности, однако посчитать, чему равняется $$$n$$$-й элемент, не может. Помогите Незнайке определить $$$n$$$-й элемент.