The program is the tool. The app is its handle. And software is the whole toolbox.
Your phone by itself is an empty toolbox. It does nothing until you put tools in it. Instagram is a tool - it shows photos. The calculator is a tool - it calculates. Every tool inside was written by someone, to do exactly one task instead of you.
That task, hidden inside the tool, is called a program. It's a sequence of commands, written in advance, that the machine follows the same way every time. Press the calculator's button, and it doesn't think - it just runs the program built into it long ago.
The app is the program dressed in a screen you look at, and buttons you touch. That outfit makes it comfortable for you. Underneath, it's still the same program - code doing the work.
Software is the umbrella over everything listed. Say "install software" or "update the app", and you're talking about the same thing - putting a new tool in the box or improving an old one, so it does its job better.
Here's where I trip up
As a designer the difference for me has always been this - the program is the tool itself, the app is the handle that fits your hand. When I make an interface, I fix the handle: I make it comfortable, clear, beautiful. The code underneath does the work, but you never see it, if I've done my part right.
So when you hear "update the software", don't panic. They're just swapping a tool in the box for a newer one, or touching up the handle to make it more comfortable for you.