Othinus and Fiamma of the Right failed. By the time Touma Kamijou arrived, Othinus had been subjected to "fairy-fication," losing her Magic God powers and suffering severe, life-threatening injuries. Fiamma of the Right had also completely vanished.

Othinus, who had been forced into fairy-fication, transformed from an imperfect Magic God with a $50\%$ probability into a different kind of perfect Magic God with a $100\%$ failure rate.

"Small-scale battles are such a hassle. Let me just end the world!" As she declared, everything was destroyed.

When Touma woke up, he found himself in total darkness, standing on a flat, featureless plane extending to infinity. There was nothing there but himself and Othinus.

"I didn't just destroy the tiny planet called 'Earth'," Othinus said.

Touma insisted that Othinus was lying, so Othinus told him to confirm it for himself. Touma walked through the darkness, not knowing how long he had been walking, until his legs gave out. There was only darkness and silence; no mountains, no rivers, no sun, moon, or stars.

Othinus knew that if she killed Touma, the Imagine Breaker would simply reside in someone else. Therefore, the best way was to erase Touma's will to resist, sealing the power of the Imagine Breaker within him forever. But Othinus was a god; she didn't need to personally crush a human's will. At that moment, the Gungnir shone brightly. Othinus wanted Touma to realize how insignificant his previous actions were, and the world was instantly engulfed in light.

Touma woke up on a bed on the second floor of a house without a ceiling. There was a smell of burning, and the starry sky was as peaceful as ever. A news report played on the television in the room: "The multi-national coalition's operation to eliminate Touma Kamijou is underway. Seventy percent of District 23 has been reduced to ruins, and Touma Kamijou's status is unknown."

Touma was bewildered. Only then did he notice the city-wide power outage and the fires burning everywhere. The television switched to the President of the United States, who declared that the strikes would not stop until Touma's death was confirmed. Although it was impossible to judge whether the act of sacrificing innocent people to strike at Touma Kamijou was just, people a hundred years from now would surely praise this action. Because if Touma Kamijou were spared now, only ruins and wreckage would remain in a hundred years. Just as Touma guessed this was an intelligence war to lure out "GREMLIN," Othinus appeared behind him and used a remote control to change the channel. World leaders were reporting on Touma's crimes and the decision to kill him.

"What did you do to those people!" Touma shouted. Othinus claimed she hadn't threatened them; this was not a dream or a hallucination, but a real world created by Othinus, and she warned Touma that he would die if he didn't leave. At that moment, two people arrived with flashlights to investigate why the TV was on. They smashed the glass, and Touma hid. But unexpectedly, they didn't enter the house; instead, they set it on fire. Touma jumped out from the second floor, and after landing, someone fired at him. Touma noticed that the two people were actually police officers. After shaking them off, Touma rested by a utility pole. Othinus stood on top of the pole, congratulating Touma on passing the initial trial, and told him she hadn't done anything—she had simply changed their perspective.

Othinus's voice echoed, "When you used your fists to defeat enemies and protect others, and when you made an indelible contribution to ending the Third World War, you were treated as a hero and naturally sought after. The positive completely covered the negative—that was the original world. But if the perspective is changed, you use your fists against everyone who opposes your opinion, even influencing the entire course of the Third World War with your fists. Such behavior is worse than that of any dictator—this is the current world. I didn't brainwash those people; I simply showed your negative side to the world."

On the road, Touma saw many people dying of hunger, and the city of the past had turned into ruins. Immediately after, the multi-national coalition launched airstrikes on all places where Touma might be hiding, and all places accepting refugee students were bombed. Touma was desperate to confirm his parents' safety when suddenly a kitchen knife was plunged into his back. Touma fell to the ground, and Komoe-sensei pulled out the knife, apologizing to Kamijou, but she could not tolerate other students suffering. On a distant television, Touma's parents appeared, publicly admitting that Touma was their son. Komoe, holding the bloody knife, walked toward Touma again, weeping.

Touma's parents requested on television that they be allowed to execute their son themselves, and asked everyone to forgive them for the sin of giving birth to Touma. As Komoe raised the knife again, Othinus squatted in front of Touma and asked, "People see your name, your appearance, and your deeds, and then arbitrarily decide what kind of person you are. Yet, if the perspective is changed, even if what you did hasn't changed in the slightest, they will still burn you, chase you, beat you, and even kill you. If someone could see you correctly, at least one person would come to save you, right? Yet, in the end, no one understands the real you. Is such a person worth saving?"

Touma still replied, "Even so, they are worth saving."

Othinus said Touma was hopeless. Then she snapped her fingers, and Komoe swung the knife down...

Touma opened his eyes and found himself napping at his desk during lunch break. His body was uninjured; it was just a nightmare! Touma sighed in relief.

Then, Touma discovered that someone with a completely different height, weight, facial features, and hair color than his own was being treated by everyone as the real Touma Kamijou. And Touma Kamijou himself was sitting alone on a chair in the classroom that no one noticed...

This was the "Infinite Hell" created by Othinus to destroy Touma Kamijou's will: constantly creating new worlds, denying the meaning of Touma's existence, and killing him in different ways to destroy the world.

Touma had thought about giving up, but in the end, he decided to follow his own will and challenge the Magic God. Even though Othinus could kill him with a flick of her finger, even though he had already died hundreds of billions of times.

In one of these worlds, Othinus gave Touma all integers from $1$ to $n$.

Touma must divide these numbers into three sets (which can be empty), such that the sum of any two elements belonging to different sets is not in the remaining set. The sets are unordered.

For example, $\left\{4\right\},\left\{2,6\right\},\left\{1,3,5\right\}$ is a valid partition for $n=6$. However, $\left\{1,2,4\right\},\left\{3,6\right\},\left\{5\right\}$ is not, because $2+3=5$.

Othinus demanded that Touma calculate the number of such partitions modulo $998244353$, or else she would kill him.

Touma never studied OI, so he couldn't do it. But fortunately, you exist in this world. Please help him find the number of ways.

Input

A single positive integer $n$.

Output

Output a single integer representing the answer modulo $998244353$.

Examples

Input 1

11

Output 1

1092

Input 2

4

Output 2

9

Input 3

514

Output 3

653467211

Constraints

• Subtask 1 (4%): $n \le 10$
• Subtask 2 (13%): $n \le 40$
• Subtask 3 (17%): $n \le 3\,000$
• Subtask 4 (21%): $n \le 10^6$
• Subtask 5 (22%): $n \le 10^9$
• Subtask 6 (23%): $n \le 2 \times 10^{10}$