Almighty Allah told us this story in the Quran: He inspected the birds, and said: "What is the matter that I see not the hoopoe? Or is he among the absentees? I will surely punish him with a severe torment, or slaughter him, unless he brings me a clear reason. But the hoopoe stayed not long, he (came up and) said: "I have grasped (the knoweldge of a thing) which you have not grasped and Ihave come to you from Sheba with true news. I found a woman ruling over them, and she has been given all things that could be possessed by any ruler of the earth, and she has a great throne. I found her and her people worshpping the sun instead of Allah, and Satan has made their deeds fair-seeming to them, and has barred them from (Allah's) Way, so they have no guidance."
Al-La (this word has two interpretations) As Satan has barred them from Allah's Way so that they do not worship (prostrate before) Allah, or so that they may worship (prostrate before) Allah, Who brings light to what is hidden in the heavens and the earth, and knows what you conceal and what you reveal. Allah, La ilaha illa Huwa (none has the right to be worshiped but He), the Lord of the Supreme Throne!
(Solomon) said: "We shall see whether you speak the truth or you are (one) of the liars. Go you with this letter of mine, and deliver it to them, then draw back from them, and see what (answer) they return." Surah 20-28