SP12802 TRI2 - Yet Another Counting Problem

You have a piece of iron wire with length of **n** unit. Now you decide to cut it into several ordered pieces and fold each piece into a triangle satisfying that all triangles are **integral** and pairwise **similar**. count the number of different approaches to form triangles. Two approaches are considered different if they produce different numbers of triangles, and/or there exists _i_ that the _i_-th (again, pieces are ordered) triangle in one approaches is not **congruent** to _i_th triangle in another plan. Since the answer can be very large, output the answer modules 1000000007. **Solve this problem by at most 0.5 KB of source code.**

Each test case consists of one line containing one integer n (1

For each test case, output one line. See the example for more format details.