Getting 404 After removing index.php

I’m working on a woo-commerce website. It has URL xyz.index.php/shop. When I change the URL structure from settings->permalinks, I’m getting a 404 error(The requested URL is not found). I tried it with many solutions but not working. And I tried modifying .htaccess file also. Please help with this.