When Darth Vader gets bored, he sits down on the sofa, closes his eyes and thinks of an infinite rooted tree where each node has exactlynsons, at that for each node, the distance between it an itsi-th left child equals todi. The Sith Lord loves counting the number of nodes in the tree that are at a distance at mostxfrom the root. The distance is the sum of the lengths of edges on the path between nodes.
But he has got used to this activity and even grew bored of it. ‘Why does he do that, then?’ — you may ask. It’s just that he feels superior knowing that only he can solve this problem.
Do you want to challenge Darth Vader himself? Count the required number of nodes. As the answer can be rather large, find it modulo109+7.
，我等你用尽了所有的哀伤；而你眼中却有我所不懂的凄凉。
