Given L is a regular language, prove that Perm(L) is Context-Free

Given a regular language $L$ defined over $Sigma = {0, 1}$. We define a new language $$Perm(L) = {w mid exists x in L, w in perm(x)}, $$ where $perm(x)$ is the set of all permutations of the word $x$.

We have to show that $Perm(L)$ is context-free.

I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.

Hint: Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.

I am unable to use this hint to proceed further. Any help is appreciated!