Woocommerce Permalink Issue – Product Category

Hi Everyone.

I want my permalinks to read website name/store/product category name/ product name. If I use the following settings:

Product category base: Store
Product permalinks > custom base: /store/%product_cat%

Then my product page is perfect, the url reads right and the top of the page has . This is exactly what I want on the product page, however the issue is that the product category page cannot be found (although the url for it is perfect).

If I instead change to the following:

Product permalink > custom base: /store/%product_category%

Then the product category page is perfect with perfect url and Home/Men’s Clothing at top of page. However, now the product page does not exist and the url has store/%product_category%/ product name in it.

Further, if I try:

Product tag base: Store
Product permalinks > custom base: /store/%product_cat%

Then both the product category page and product page do actually work with the perfect url, but the links on the top of the page read:
Home / Products Tagged ‘Men’s clothing’ and Home / Mens Clothing / (product name).

This would as a last resort be okay, but I think looks unprofessional. I want both of them to read Home/ Men’s Clothing. And the url to be website/store/product category name/ product name.

Is there something I am doing wrong here?

Thanks
Caleb