CAIRO (Reuters) - Mohamed Mursi, Egypt's first freely elected president whose powers have already been curbed by the army, began work on a coalition on Monday after touring his new palace, once home of Hosni Mubarak who banned his movement for three decades.
Declared winner on Sunday a week after a tumultuous run-off vote that pitted him against a former air force chief, the Islamist faces the challenge of meeting sky-high expectations in a nation tired of turmoil while the economy is on the ropes.
But his campaign pledge to complete the revolution that toppled Mubarak last year but left the pillars of his rule intact will come up against the entrenched interests of the generals who are in charge of the transition to democracy.
Shortly before the historic presidential vote, a newly elected Islamist-led parliament was dissolved by the army based on a court order, and the generals issued a decree setting limits on the president's remit, which cuts into Mursi's powers to act but exposes him to blame for any failures.
Critics at home and in the West called it a "soft coup".
One pressing concern - on which many Egyptians are likely to judge his performance - will to be to revive the economy of the world's most populous Arab nation.
Monday's stock market rally, at least partly fuelled by relief that the vote and result passed off without violence, may encourage the new president, but he still has to prove to wary longer-term investors that Egypt is on the road to recovery.
Egyptian newspapers welcomed Mursi's win over Ahmed Shafik, Mubarak's last prime minister, as a victory for the people, although many more liberal-minded Egyptians worry his conservative group will slowly whittle away at social freedoms.
Further afield, his win has had an immediate impact beyond Egypt's borders, inspiring Islamists who have risen up against autocrats across the Middle East and swept to power in North Africa. Israel worries its 1979 peace deal with Egypt, never warm, will cool further.
Palestinians in Gaza, however, are delighted.
Iran saw his election as an "Islamic awakening" - though Tehran and the Muslim Brotherhood follow different, often opposing forms of the faith. Iran's Fars news agency published an interview in which Mursi called for restoring full ties between Cairo and Tehran to build strategic "balance". A Mursi aide said he gave the interview 10 days ago.
A security official said Mursi, 60, and his wife took a tour of their new home, once Mubarak's main residence - a dramatic change of fortunes full of symbolism for a former political prisoner whose group was pursued remorselessly during Mubarak's 30-year rule.
An aide said Mursi then went to the Defence Ministry for talks with the head of the ruling military council's Field Marshal Hussein Tantawi and the army-appointed Prime Minister Kamal al-Ganzouri. They discussed forming a new government at the meetings, which Egyptians will see as a sign that real power still lies with the army.
As president, Mursi can appoint the cabinet. His aides say he has already reached out to politicians from outside the Brotherhood such as reformist Mohamed ElBaradei, who has yet to publicly respond. But legislative powers remain with the army while the parliament is dissolved, restricting his power to act.
Egypt's army-appointed government, led by al-Ganzouri who also served in the 1990s as prime minister under Mubarak, submitted its resignation on Monday but was asked to stay on temporarily until Mursi, who has yet to take the oath of office, put a team together, Information Minister Ahmed Anis said
"The revolution reaches the republican palace," wrote Al-Shorouk newspaper. Another, Al-Akhbar, quoted from Mursi's victory speech: "I am a servant of the people and an employee of the citizens".
It is a sentiment widely spoken: the sense that at last, perhaps, Egyptians have a leader who can be "fired".
Celebrations in Cairo's Tahrir Square - theatre of the revolution that overthrew Mubarak - extended through the night. Some Brotherhood followers were still celebrating, surprised by their victory that broke a six-decade tradition of presidents plucked from the military.
"It was a little surprising that the army acknowledged his win," said 40-year-old teacher Adel Mohamed who was in the square when the result was declared after a nervous week's wait since the vote. "The pressure from the street, from the revolution, will give Mursi strength to negotiate."
From Syria's opposition who are seeking the downfall of President Bashar al-Assad came word that Cairo was again a "source of hope" for a people "facing a repressive war of annihilation".
But millions of Egyptians, and the Western powers, looked on with unease at the prospect of the long-suppressed Brotherhood making good on its dream of an Islamic state.
Israel has been particularly nervous, urging its neighbour to respect their peace deal. It worries that the Brotherhood's win will embolden Palestinian Islamists opposed to Israel.
"Darkness in Egypt," headlined Israeli paper Yedioth Ahronoth. Israeli Prime Minister Benjamin Netanyahu said he "respected" the result and said he saw future cooperation with the new administration.
An aide to Mursi said during Mursi's campaign that he would delegate meetings with Israeli officials to his foreign minister, unlike Mubarak who often met top Israelis. Mubarak went to Israel only once, for the funeral of assassinated Prime Minister Yitzhak Rabin.
"Mursi's victory is most likely to strengthen the hand of Hamas in its fight against Israel because it will give it a moral boost," said political scientist Mustapha al-Sayyed.
But the army, determined not to see its $1.3 billion in U.S. military aid a year jeopardised, will probably ensure ties are not undermined even if the relationship sours, diplomats say.
Pledging to uphold international treaties, in a gesture to Israel, Mursi said in his first televised address as president-elect that he would work with others to see the democratic revolution through.
"There is no room now for the language of confrontation," he said, a message addressed not just to the army but to the young, urban revolutionaries who launched last year's uprising only to see the Brotherhood dominate the political scene afterwards.
One of the most influential revolutionary youth groups greeted Mursi's win as a victory for last year's uprising.
"We have defeated the candidate of Mubarak's military state, the candidate of the corrupt 'deep state' that we are fed up with," said the April 6 Youth movement.
"Starting today we will work as one body for Egypt."
Western powers congratulated Mursi, who received a phone call from U.S. President Barack Obama, offering help.
The White House said in a statement: "The president underscored that the United States will continue to support Egypt's transition to democracy and stand by the Egyptian people as they fulfil the promise of their revolution."
Mursi may have little choice but to compromise with the army, and Brotherhood sources said a package of agreements discussed with generals last week could soon be announced.
The Brotherhood's political gains, first winning the biggest bloc in parliament and then running for president, had rattled the military. With the help of a Mubarak-era judiciary, the military council dissolved parliament on the eve of the presidential vote, then gave itself the legislative power.
Senior Brotherhood officials say they have been negotiating in the past week to change some of that, though both sides deny any haggling over the result of the presidential vote itself.
"President Mursi and his team have been in talks with the military council to bring back the democratically elected parliament and other issues," Essam Haddad, a senior Brotherhood official, told Reuters on Monday.
Brotherhood sources told Reuters they hoped the army might allow a partial recall of parliament and other concessions in return for Mursi exercising his powers to name a government and presidential administration in ways the army approves of - notably by extending appointments across the political spectrum.
Military officials have confirmed discussions in the past few days but had no immediate comment on the latest talks.
Brotherhood officials have said they will press on with street protests to pressure the army but this, along with a number of other contentious issues including to whom and where Mursi swears his oath of office, could be settled soon.
The army wants Mursi sworn in on June 30, meeting a deadline it set itself for handing over Egypt to "civilian rule" - although the military's influence will go on long beyond that.
Additional reporting by Tamim Elyan; Writing by Edmund Blair; Editing by Alastair Macdonald