Using random and shutil to move files in loop in python

I have a small problem. I am trying to move 20x500 images in 20 predefined folders. I can make this work with just 500 random images and I have identified the problem; I draw 500 random files, move them and then it tries doing it again but since it doesn't update the random list, it fails when it reaches an image that it thinks is part of the random group but it has already been moved and thus fails. How do I "update" the random list of files so that it doesn't fail because I move stuff? The code is:

import os
import shutil
import random

folders = os.listdir(r'place_where_20_folders_are')
files = os.listdir(r'place_where_images_are')
string=r"string_to_add_to_make_full_path_of_each_file"

folders=[string+s for s in folders]

for folder in folders:
    for fileName in random.sample(files, min(len(files), 500)):
        path = os.path.join(r'place_where_images_are', fileName)
        shutil.move(path, folder)