Wordpress Clean Urls Don't Work

I am trying to use the following code in my .htaccess file:

RewriteEngine On

RewriteBase /

RewriteRule ^index.php$ - [L]

RewriteCond %{REQUEST_FILENAME} !-f

RewriteCond %{REQUEST_FILENAME} !-d

RewriteRule . /index.php [L]

It works on other servers that run apache.

However it doesn't work on my virtualmin server. I have checked for AllowOveride all and it is there. I have also tried to write my own php script and use mod rewrite to rewrite the root but it doesn't work. I have to go to domain.tld/index.php/enter_page_name_here instead of domain.tld/enter_page_name_here.

Thanks.