How does Baku work with Prince Malchezaar?

Baku enhances your hero power at the start of the game when you create a deck of only odd cards. Prince Malchezaar puts 5 random legendaries into your deck at the start of the game, which could be odd or even.

What happens with both of them in the same deck? Does Baku still upgrade your hero power?

Yes, you get the benefit of both cards even if Prince Malchezaar adds an even-cost legendary card into your deck.

Test procedure I followed:

1. Build a deck containing Baku the Mooneater, Prince Malchezaar, and odd-cost cards (choosing draw abilities to help get the test done).
2. Start a game (Practice mode).
3. Observe that both Malchezaar and Baku show their Start of Game animations, and that one's Hero Power is upgraded.
4. Play to draw cards until an even-cost legendary card appears (this will not necessarily happen in every game).

I noticed that Malchezaar's animation consistently plays before Baku's, which is the opposite of what you would expect if the only reason they don't interfere is an accident of effect ordering.