Ceci est un problème À POINTS (SCORED). Il y a dix sous-groupes de données. Les sous-groupes seront évalués indépendamment. Résoudre toutes les données d'un sous-groupe rapportera $0.1$ problème (c'est ainsi que cela apparaîtra sur le tableau des scores, mais la réponse de Kattis peut afficher $10$). Résoudre toutes les données des dix sous-groupes rapportera $1$ problème complet. Vous pouvez continuer à soumettre pour essayer d'améliorer votre score.
La pénalité de temps pour ce problème sera évaluée comme suit :
Un point pour chaque minute écoulée depuis le début du concours jusqu'à la dernière soumission ayant augmenté votre score.
Vingt points pour chaque soumission antérieure à cette dernière soumission ayant augmenté le score et qui n'a pas augmenté votre score, à l'exception des erreurs de compilation, qui ne donnent lieu à aucune pénalité.
Aucun point de pénalité n'est appliqué si votre score ne dépasse jamais zéro.
Vous souvenez-vous de la chanson « Les 12 jours de Noël » ("The 12 Days of Christmas") ?
« Le premier jour de Noël, mon grand amour m'a donné une perdrix dans un poirier. »
Super. Je voulais un iPhone.
« Le deuxième jour de Noël, mon grand amour m'a donné deux tourterelles et une perdrix dans un poirier. »
Bon, maintenant j'ai quatre oiseaux : deux tourterelles et une perdrix aujourd'hui, plus une perdrix d'hier. Mes chats deviennent fous.
« Le troisième jour de Noël, mon grand amour m'a donné trois poules françaises, deux tourterelles et une perdrix dans un poirier. »
C'est quoi cette histoire d'oiseaux ? Cela en fait six de plus aujourd'hui, j'en ai donc maintenant dix, et aucun endroit où les mettre (sauf à l'intérieur des chats). Combien de temps mon grand amour va-t-il pouvoir continuer ainsi ?
Étant donné un entier $n$, combien de cadeaux ai-je reçus après $n$ jours ? Comme cette valeur peut être grande, affichez-la modulo $998\,244\,353$.
Entrée
L'unique ligne d'entrée contient un entier $n$, qui représente le nombre de jours pendant lesquels mon grand amour m'offre des cadeaux.
Il y a dix sous-groupes de données, chacun avec des limites différentes sur $n$ :
($1 \le n \le 10$)
($10 < n \le 1\,000$)
($1\,000 < n \le 10^5$)
($10^5 < n \le 10^7$)
($10^7 < n \le 10^9$)
($10^9 < n \le 10^{11}$)
($10^{11} < n \le 10^{13}$)
($10^{13} < n \le 10^{15}$)
($10^{15} < n \le 10^{17}$)
($10^{17} < n \le 10^{18}$)
Sortie
Affichez un seul entier, qui correspond au nombre de cadeaux que je reçois après exactement $n$ jours. Comme ce nombre peut être très grand, affichez-le modulo $998\,244\,353$.
Exemples
Entrée 1
1
Sortie 1
1
Entrée 2
2
Sortie 2
4
Entrée 3
3
Sortie 3
10