Given that you have a very specific product, target audience, and list of locations, I'd recommend testing AdWords campaigns. Depending on what your product is, you'll likely be able to identify some niche keywords to bid on, and you can segment your campaigns by geography, allowing you to get really localized with your ad copy.

Feel free to shoot me a message if you'd like to discuss this further!