For the largest k=2^29-1, the standard solution (STD) use about 500 vertices, but my solution only use less than 100 vertices (exactly 92).

For example, if needs 1 path, add an edge between 61 & 92. if needs 2 paths, add an edge between 59 & 91. More commonly, if needs 2^n paths, add an edge between 61-n*2 & 92-n.

For the input k, transform k to binary type. For example k = 9 = (1001)2. Add edges between 61 & 92, 55 & 88.

You can view my code here 5891486

PS. Taube 5886357 seems to have a better solution for he use less than 90 vertices.