Is every positive integer the permanent of some 0-1 matrix? In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:

Is it true that for every positive integer $k$ there exists a balanced bipartite graph with exactly $k$ perfect matchings?

Equivalently, as stated in the title, is every positive integer the permanent of some 0-1 matrix?
The answer is surely yes, but it is not clear to me how to prove it.  Entry A089479 of the OEIS reports the number $T(n,k)$ of times the permanent of a real $n\times n$ zero-one matrix takes the value $k$ but does not address the question of whether, for every $k$, there exists $n$ such that $T(n,k)\ne 0$.  Assuming the answer is yes, the followup question is, what else can we say about the values of $n$ for which $T(n,k)\ne 0$ (e.g., upper and lower bounds)?
 A: The answer to the question is yes. Given $k$, the 0-1 matrix given by 
$1$ $1$ $\dotsc$ $1$ $0$ $0$ $\dotsc$ $0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$  $\dotsc$ $0$ $0$ $\dotsc$ $0$ $0$ $0$
$0$ $0$ $1$ $1$ $0$ $\dotsc$  $0$ $\dotsc$ $0$ $0$ $0$
$\dotsc$
$1$ $0$ $0$ $0$ $0$ $\dotsc$ $\dotsc$ $0$ $0$ $0$  $1$
where the first row has precisely $k$ entries equal to $1$, evidently has permanent equal to $k$.
For $k=1$ the matrix is ($1$). For $k=2$ the matrix is 
$1$ $1$
$1$ $1$
For $k=3$ the matrix is 
$1$ $1$ $1$
$0$ $1$ $1$ 
$1$ $0$ $1$.
For $k=4$ the matrix is 
$1$ $1$ $1$ $1$ 
$0$ $1$ $1$ $0$
$0$ $0$ $1$ $1$
$1$ $0$ $0$ $1$
which evidently has permanent equal to $4$.
Please note that also, for each given $k$ and $1\leq \ell \leq k$, this construction can be tweaked to give an explicit $k\times k$ sized $0$-$1$-matrix having permanent precisely $\ell$, just by making the first row have precisely $\ell$ entries equal to $1$. 
Please also note that my construction does not have any bearing on the interesting and apparently difficult question which was cited in the present OP: my construction is too wasteful: it utilizes a $k\times k$ matrix, which is far too large when it comes to meet the demands of the OP in said question.
A: If an order n (0,1) matrix has r rows with all ones, its permanent is a multiple of r! by an easy argument.  It follows that the largest odd number which is a permanent of an order n matrix is q = der(n) + der(n-1), which is a sum of numbers of derangements, and is a little larger than $n!/e$.  I suspect that the smallest positive number not expressible as a permanent of this size matrix is an odd integer which is not much smaller, perhaps about half, of q.  If so, then we can shave a little bit off of n=log(k) in the construction in Timothy Chow's post.  For some motivation for this problem, look at Will Orrick's talk mentioned (for determinants)  at https://mathoverflow.net/a/271273 .
Gerhard "Also A Potential Polymath Project" Paseman, 2017.08.29.
A: For the record, here is the construction of Kim, Lee, and Seol that I alluded to in my comment to Peter Heinig's answer.
Write $k-1$ in binary, and let $n$ be 1 plus the number of binary digits of $k-1$.
Start with an $n\times n$ matrix with all $1$'s on or above the main diagonal and all $0$'s below the diagonal.  Then replace the  first $n-1$ entries of the bottom row of the matrix with the binary representation of $k-1$ (one bit per entry).
For example, if $k=389$, then $k-1$ in binary is $110000100$.  Then $n=1+9=10$ and the matrix is
$$\matrix{
1&1&1&1&1&1&1&1&1&1\cr
0&1&1&1&1&1&1&1&1&1\cr
0&0&1&1&1&1&1&1&1&1\cr
0&0&0&1&1&1&1&1&1&1\cr
0&0&0&0&1&1&1&1&1&1\cr
0&0&0&0&0&1&1&1&1&1\cr
0&0&0&0&0&0&1&1&1&1\cr
0&0&0&0&0&0&0&1&1&1\cr
0&0&0&0&0&0&0&0&1&1\cr
1&1&0&0&0&0&1&0&0&1\cr
 }$$
