The problem comes from the fact that your Vim setup supports python, but python is not installed on your system.
When Vim has the
'python3' features enabled that means that it provides an interface to interact with python code: you can make Vim to ask the system to execute a python statement or a whole python code.
Even if the interface is enabled, Vim is not a python compiler/executer: you still need to install them on your system so that Vim can make a call to these tools. See this page to get the executable to install python.
In the comments OP also had a question about which version of python (python2 or python3) to install:
Here python was needed to make UltiSnips working, as UltiSnips doesn't recommend a specific version I'd recommend to install whatever version you want, both should work. Remember that it is possible to install several version of python on the same system.