Guys, i need help with this problem from a offline contest i participated ;(

Construct a directed graph that sastified all the following conditions:

• at most 1 edge between any pair of nodes

• the graph must have at most 500,000 nodes and 1,000,000 edges

• graph must be acyclic (no cycle)

• must be exactly k ($$$k\le10^{100}$$$) distinct paths from node 1 to the node with largest index (node n)

Thank yall!