667 . Induced subgraphs
Description
A vertex-induced subgraph (sometimes simply called an "induced subgraph") is a subset of the vertices of a graph G together with any edges whose endpoints are both in this subset. (from Wolfram MathWorld)
For a graph G, we say G is a path of length 3 if G has exactly 3 vertices v1, v2, v3, and exactly two of the edges from {(v1,v2), (v2,v3), (v3,v1)} is an edge of G. Usually we call it P3.
So, here is the problem: How many kind of graphs of n nodes that do not have a P3 as its vertex-induced subgraph? Note that the vertices are not labeled. For example, when n=4, we have exactly 5 graphs.
Input Format
There are multiple test cases in the input file.
Each test case is in a line contains a number n(1<=n<=100,000).
n = 0 indicates the end of input, do not proceed it.
Output Format
For each test case, output the number modulo 1000000007.
Sample Input 1
1 2 3 4 0
Sample Output 1
1 2 3 5
Hints
Problem Source
Migrated from old NTUJ.
classical problem, modified by tmt
Subtasks
| No. | Testdata Range | Score |
|---|