Trineq

J. Trineq

== include(page="template/taskheader" task_id="trineq") ==

În această problemă trebuie să număraţi în câte feluri pot fi etichetate muchiile unui graf complet cu $N$ noduri cu lungimi din mulţimea ${0, 1, 2}$ astfel încât oricare triplet de noduri din cele $N$ să respecte inegalitatea triunghiului: suma lungimilor celor mai mici două laturi este mai mare sau egală cu lungimea celei mai mari muchii.

În această problemă trebuie să număraţi în câte feluri pot fi etichetate muchiile unui graf complet cu $N$ noduri cu lungimi din mulţimea ${0, 1, 2}$ astfel încât oricare triplet de noduri din cele $N$ să respecte inegalitatea triunghiului: suma lungimilor celor mai mici două muchii este mai mare sau egală cu lungimea celei mai mari muchii.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $trineq.out$ se vor afla $T$ linii, fiecare conţinând răspunsul la cerinţa problemei *modulo 1.000.000.007*.

În fişierul de ieşire $trineq.out$ se vor afla $T$ linii, fiecare conţinând răspunsul la cerinţa problemei *modulo 1000000007*.

h2. Restricţii

* $1 ≤ T ≤ 1000$
* $1 ≤ N ≤ 1000$

* $1 ≤ T ≤ 2000$
* $2 ≤ N ≤ 2000$
 

h2. Exemplu
table(example). |_. trineq.in |_. trineq.out |
| 1
3

|

| 15

|
== include(page="template/taskfooter" task_id="trineq") ==