Custom Post Type URL Structure

Let’s say I have a site with a custom post type called “locations”. Each of those locations fall under a country and state. This is the URL structure I’m trying to accomplish:

/locations/canada/british-columbia/<post-name>

I would then want an index page for “locations” (listing all the locations) , “canada” (listing only the locations in canada) and “british-columbia” (listing only the locations in BC.

Does anyone know how to accomplish this?