$n$ саны берілген. Сіздің міндетіңіз — барлық үшбұрышты тізбектерді санау және олардың санын $10^9 + 7$ санына бөлгендегі қалдықты шығару. Егер тізбек келесі шарттарды қанағаттандырса, ол үшбұрышты тізбек деп аталады:

• Тізбектің ұзындығы $n$-нен аспайды.
• Әрбір элемент $[1, n]$ аралығындағы бүтін сан болып табылады.
• Осы тізбектің қандай да бір үш элементі азғындалмаған үшбұрыштың* қабырғаларының ұзындықтары бола алады.

$n = 100$ үшін үшбұрышты тізбектердің мысалдары: $(1, 1, 1)$ және $(16, 1, 11, 25, 100)$. Біріншісінде азғындалмаған үшбұрыштың қабырғалары $(1, 1, 1)$, ал екіншісінде $(16, 11, 25)$.

$(16, 1, 11, 84, 100)$ тізбегі үшбұрышты емес, өйткені ешқандай үш элемент азғындалмаған үшбұрыштың қабырғаларын құрамайды. $(5, 5)$ тізбегі де үшбұрышты емес.

* Егер үшбұрыштың ауданы оң болса, ол азғындалмаған деп аталады. Баламалы түрде, оның төбелері бір түзудің бойында жатпайды.

Кіріс деректер

Жалғыз жолда бір бүтін сан $n$ ($3 \le n \le 200\,000$) берілген.

Шығыс деректер

Бір бүтін санды — үшбұрышты тізбектер санын $10^9 + 7$ (яғни $1000000007$) санына бөлгендегі қалдықты шығарыңыз.

Мысалдар

Кіріс деректер 1

3

Шығыс деректер 1

15

Кіріс деректер 2

4

Шығыс деректер 2

254

Ескертпе

$n = 3$ үшін $15$ үшбұрышты тізбек бар: $(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$.

$n = 4$ үшін $254$ үшбұрышты тізбек бар: $(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$.