When the COO personally calls you to say that they shouldn't have fired you and they need you for a big project that nobody else is able to take on right now, it usually means they're motivated to get you back.
So that's a great opportunity, but you'll need to put in some work to take full advantage of it.
The first thing to do is decide if you even want your job back. Maybe you do, maybe you don't. Give it some serious thought.
If you do want your job back, now would be an excellent time to negotiate a raise.
So what you need to do is figure out roughly what you're worth to the company. You'll need to put some work in here. Look at job openings, talk to recruiters, do some market research.
Try to figure out how badly they want to keep you. Would it be painful for the company to lose you for this project, or merely an inconvenience?
Put all that together and you should get a sense of where you should be aiming for. Chances are, it'll be significantly more than you're currently being paid.
Then you have to go and negotiate. Decide if you're willing to walk away if you don't get a deal, because that will have a big impact on how you want to word your response. Only you can guess what will work best in your company, but here's my best guess at how I'd do it (and this is assuming you are willing to walk away):
Thank you for reaching out.
It's an unfortunate situation. I had hoped to stay with [company]. My work seemed to be valued, I was
advancing professionally and taking on bigger and more important projects and I saw a path to continuing on that
But if the company is willing to make me redundant at a moment's
notice, then that's a very clear signal I was wrong and I should
find someone new to work for. Who values my results and is
willing to invest in my ongoing professional development.
If you think that can still be [company], then let's have that
conversation. If not, then thank you again for reaching out and I will
continue handing over my outstanding projects and responsibilities as
per my redundancy notice.
The goal is to frame things to your advantage:
Get them thinking about how you were a committed and valuable employee that they don't want to lose. About those bigger and more important projects which are about to grind to a halt without you.
Make it clear that you are holding them to their redundancy notice. If they want to take it back then it's not gonna be free.
Frame the next steps as being about value, compensation, and professional development.
Suggest that you might stay if the value/compensation/development picture changes, but they're going to have to work extra hard to convince you given what just happened.
Remind them that you are currently leaving. Right now. So if they want to fix that, then they need to act quickly. And a nice reminder at the end that they don't have someone to take over your responsibilities and it would be painful to lose you.
And you do all of that without calling them out or getting confrontational.
Then you see what happens.
Either they'll decide to just eat the loss, wish you good luck and you need to go find a new job.
Or they'll take the hint and try to negotiate. Which is a whole different category of questions which you should make sure you're prepared for because these things can move very quickly when an executive decides to make something happen.
If you want somewhere to start, I highly recommend https://www.kalzumeus.com/2012/01/23/salary-negotiation/
And just as an aside:
Don't let anyone tell you you're too young and inexperienced to be paid what you're worth for the job you're already doing. My last company told me at 24 that I was getting ahead of myself and comparing my salary to positions that needed [Qualifications] and [Years of experience] which I didn't have. Less than a year later they offered me a 100% raise and equity in the company to stop me leaving.
Figure out what you're actually worth to the company, what value you deliver, what it would cost them to replace you, and negotiate based on that number.