#include<bits/stdc++.h>

#include "inv.h"

typedef long long ll;

const int P=998244353,P2=P/2;

const int V1=243713,V2=7615,V3=2729407,VX=10000;
const int tab1[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,90,1,1,1,1,81,1,78,1,75,74,1,71,70,69,68,67,66,64,127,63,62,61,60,59,58,57,113,56,55,54,107,53,52,103,51,50,50,49,97,48,47,47,46,46,45,45,44,44,43,43,85,42,83,41,41,40,40,79,39,39,77,38,38,75,37,37,73,36,36,71,35,35,69,34,34,34,67,33,33,98,65,32,32,95,63,31,31,92,61,30,30,30,59,88,29,29,29,57,85,28,28,28,55,55,27,27,27,80,53,79,26,26,26,77,51,76,25,25,25,99,49,49,73,24,24,24,95,47,47,70,23,23,23,23,68,45,45,67,22,22,22,22,87,65,43,64,85,21,21,21,21,83,62,41,41,61,20,20,20,20,20,79,59,39,39,58,77,19,19,19,19,19,75,56,37,37,92,55,73,18,18,18,18,18,71,53,53,35,35,87,52,69,17,17,17,17,17,17,67,50,83,33,33,33,49,114,65,16,16,16,16,16,16,79,63,47,78,31,31,31,46,46,61,76,15,15,15,15,15,15,74,59,44,44,73,29,29,29,72,43,43,57,71,14,14,14,14,14,14,14,69,55,55,41,41,68,27,27,27,67,40,40,53,53,66,13,13,13,13,13,13,13,13,64,115,51,38,38,101,63,25,25,25,87,62,37,37,86,49,61,73,12,12,12,12,12,12,12,12,83,71,59,47,82,35,35,93,58,23,23,23,23,80,57,34,34,34,45,45,56,67,78,11,11,11,11,11,11,11,11,11,76,65,54,43,43,75,32,32,85,53,74,21,21,21,21,73,52,52,31,31,31,72,41,41,51,61,71,81,10,10,10,10,10,10,10,10,10,10,69,59,49,49,39,39,68,29,29,29,77,48,67,86,19,19,19,19,19,66,47,47,28,28,28,93,65,37,37,46,46,55,64,73,82,9,9,9,9,9,9,9,9,9,9,9,71,62,53,97,44,79,35,35,61,61,26,26,26,69,43,43,60,77,17,17,17,17,17,93,59,59,42,109,67,25,25,25,83,58,33,33,33,41,41,90,49,57,57,65,81,8,8,8,8,8,8,8,8,8,8,8,8,79,71,63,55,47,47,39,39,70,31,31,31,54,54,23,23,23,23,84,61,38,38,53,53,68,15,15,15,15,15,15,82,67,52,37,37,37,59,22,22,22,22,95,51,51,29,29,29,94,65,36,36,79,43,93,50,57,64,71,78,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,69,62,55,103,48,41,41,75,34,34,34,61,27,27,27,27,47,47,67,20,20,20,20,20,73,53,33,33,33,46,46,59,72,85,13,13,13,13,13,13,13,71,58,45,45,77,32,32,83,51,70,19,19,19,19,19,82,63,44,44,94,25,25,25,81,56,31,31,31,68,37,37,80,43,43,49,104,55,61,67,73,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,77,71,65,59,53,47,47,41,41,76,35,35,64,93,29,29,29,52,52,98,23,23,23,86,63,40,40,57,74,17,17,17,17,17,17,62,45,45,73,28,28,28,67,39,39,89,50,61,72,11,11,11,11,11,11,11,11,11,11,60,109,49,38,38,38,65,27,27,27,70,43,43,59,75,16,16,16,16,16,16,69,53,90,37,37,58,79,21,21,21,21,89,47,47,73,26,26,26,83,57,31,31,31,67,36,36,36,41,41,87,46,51,51,56,61,66,71,76,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,79,74,64,123,59,54,49,49,44,44,39,39,73,34,34,97,63,29,29,29,53,53,24,24,24,24,67,43,43,62,81,19,19,19,19,19,71,52,85,33,33,80,47,61,75,89,14,14,14,14,14,14,79,65,51,88,37,37,60,23,23,23,23,78,55,87,32,32,73,41,41,50,50,59,68,77,9,9,9,9,9,9,9,9,9,9,85,76,58,58,49,89,40,40,31,31,31,84,53,75,22,22,22,22,79,57,35,35,83,48,109,61,87,13,13,13,13,13,13,13,69,56,99,43,43,30,30,30,77,47,64,81,17,17,17,17,17,89,55,55,38,38,59,59,21,21,21,21,88,67,46,71,25,25,25,25,54,54,29,29,29,62,95,33,33,70,37,37,78,41,41,45,45,49,49,53,57,57,61,65,69,77,4,89,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,75,71,67,63,59,55,51,51,47,47,43,43,39,39,74,35,35,101,31,31,31,89,58,27,27,27,27,50,50,23,23,23,23,88,65,42,42,61,19,19,19,19,19,19,53,53,34,34,83,49,64,79,15,15,15,15,15,15,86,71,56,41,41,67,26,26,26,89,63,37,37,85,48,59,70,81,11,11,11,11,11,11,11,11,84,73,62,51,40,40,69,98,29,29,76,47,47,65,18,18,18,18,18,79,61,43,43,68,25,25,25,25,57,89,32,32,71,39,39,85,46,99,53,60,67,74,7,7,7,7,7,7,7,7,7,7,7,7,7,7,80,73,66,59,52,45,45,83,38,38,69,31,31,31,55,79,24,24,24,89,65,41,41,58,75,17,17,17,17,17,17,61,44,44,71,27,27,27,64,101,37,37,47,47,57,67,77,10,10,10,10,10,10,10,10,10,10,73,63,53,43,43,76,33,33,89,56,79,23,23,23,23,59,36,36,36,49,49,62,13,13,13,13,13,13,13,13,13,55,55,42,42,71,29,29,29,45,45,61,77,16,16,16,16,16,16,67,51,51,35,35,89,54,73,19,19,19,19,19,79,60,41,41,63,22,22,22,22,22,47,47,72,25,25,25,25,53,81,28,28,28,59,59,31,31,31,65,34,34,71,37,37,37,40,40,83,43,89,46,95,49,52,52,55,58,61,64,67,70,73,76,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,80,3,71,68,65,62,59,56,53,53,50,97,47,44,44,85,41,41,38,38,73,35,35,102,67,32,32,93,61,29,29,29,55,55,26,26,26,26,49,49,72,23,23,23,23,66,43,43,63,20,20,20,20,20,77,57,37,37,91,54,71,17,17,17,17,17,82,65,48,79,31,31,31,45,45,59,73,87,14,14,14,14,14,14,81,67,53,39,39,64,89,25,25,25,86,61,36,36,83,47,58,58,11,11,11,11,11,11,11,11,11,11,74,63,52,93,41,41,101,30,30,79,49,68,87,19,19,19,19,84,65,46,46,100,27,27,27,62,35,35,35,43,43,51,51,59,67,8,8,8,8,8,8,8,8,8,8,8,8,93,77,69,61,53,98,45,82,37,37,66,29,29,29,79,50,71,21,21,21,21,21,55,55,34,34,81,47,107,60,13,13,13,13,13,13,13,13,13,57,101,44,75,31,31,31,49,49,67,18,18,18,18,18,18,59,100,41,64,87,23,23,23,23,74,51,79,28,28,28,61,33,33,33,71,38,38,43,43,91,48,53,53,58,63,68,5,83,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,82,72,67,62,57,52,52,47,47,42,42,37,37,37,69,32,32,91,59,27,27,27,76,49,49,22,22,22,22,22,61,39,39,95,56,73,17,17,17,17,17,80,63,46,46,29,29,29,29,41,41,94,53,65,12,12,12,12,12,12,12,12,12,67,55,98,43,43,31,31,31,81,50,69,19,19,19,19,19,64,109,45,71,26,26,26,26,59,33,33,33,73,40,40,47,47,54,61,68,75,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,72,65,58,51,51,44,44,37,37,67,97,30,30,83,53,76,23,23,23,23,62,39,39,94,55,71,16,16,16,16,16,16,73,57,41,41,66,91,25,25,25,59,59,34,34,77,43,43,52,61,61,79,9,9,9,9,9,9,9,9,9,9,9,74,65,56,47,47,38,38,105,29,29,29,29,49,49,69,20,20,20,20,91,51,51,31,31,31,73,42,42,53,64,75,86,11,11,11,11,11,11,11,11,79,68,57,46,46,35,35,35,59,24,24,24,24,85,61,37,37,50,50,63,76,13,13,13,13,13,13,13,80,67,54,41,41,69,28,28,28,71,43,43,58,73,15,15,15,15,15,15,92,62,109,47,79,32,32,81,49,66,83,17,17,17,17,17,17,53,53,36,36,91,55,74,19,19,19,19,19,59,99,40,40,61,21,21,21,21,21,65,44,44,67,23,23,23,23,71,48,73,25,25,25,25,77,52,27,27,27,27,56,85,29,29,29,60,91,31,31,64,97,33,33,68,35,35,35,37,37,37,39,39,39,41,41,43,43,88,45,92,47,49,49,51,51,53,55,57,57,59,61,63,65,67,69,2,75,77,2,2,87,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2};
const int tab2[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,490,1,1,1,1,481,1,1,1,474,1,1,469,1,1,464,1,1,459,1,456,1,453,1,1,448,1,445,1,442,1,439,1,436,435,1,432,1,429,428,426,425,1,422,421,1,418,417,1,414,413,1,410,409,408,1,405,404,403,1,400,399,398,397,1,394,393,392,391,1,388,387,386,385,384,383,382,1,379,378,377,376,375,374,373,372,371,370,369,368,367,366,365,364,363,362,361,360,359,358,357,356,355,354,353,352,351,350,349,348,347,346,345,345,344,343,342,341,340,339,338,337,337,336,335,334,333,332,331,331,330,329,328,327,653,326,325,324,323,645,322,321,320,319,319,318,317,316,631,315,314,313,625,312,311,310,619,309,308,307,307,306,305,609,304,303,302,302,301,300,300,299,298,298,297,296,296,295,294,294,293,292,292,291,290,290,289,288,288,287,573,286,285,285,284,567,283,282,282,281,280,280,279,279,278,555,277,276,276,275,549,274,273,273,272,272,271,541,270,539,269,268,268,267,267,266,266,265,529,264,527,263,525,262,261,261,260,260,259,259,258,258,257,257,256,256,255,255,254,254,253,253,252,252,251,251,250,250,499,249,497,248,495,247,247,246,246,245,245,244,244,487,243,485,242,242,241,241,240,240,479,239,477,238,238,237,237,473,236,471,235,235,234,234,467,233,233,232,232,463,231,461,230,230,229,229,457,228,228,227,227,227,226,226,451,225,225,224,224,447,223,223,222,222,222,221,221,441,220,220,439,219,219,218,218,435,217,217,433,216,216,431,215,215,214,214,214,213,213,213,212,212,423,211,211,421,210,210,419,209,209,417,208,208,415,207,207,413,206,206,206,205,205,614,204,204,204,407,203,203,405,202,202,403,201,201,401,200,200,200,199,199,199,397,198,198,395,197,197,197,393,196,196,391,195,195,195,583,194,194,387,193,193,193,577,192,192,383,191,191,572,381,190,190,379,189,189,189,377,188,188,563,375,187,187,373,559,186,186,371,185,185,185,369,184,184,184,367,183,183,183,365,182,182,182,363,181,181,181,361,180,180,180,359,179,179,179,357,178,178,178,355,177,177,177,353,529,176,176,351,526,175,175,524,349,174,174,174,347,173,173,173,345,517,172,172,172,343,171,171,171,341,511,170,170,509,339,169,169,169,337,337,168,168,168,335,502,167,167,500,333,166,166,166,497,331,165,165,165,329,493,164,164,164,327,490,163,163,163,325,487,162,162,162,323,484,161,161,161,321,481,160,160,160,319,478,159,159,159,317,317,158,158,158,473,315,157,157,157,157,313,469,156,156,156,311,311,155,155,155,464,309,463,154,154,154,307,307,153,153,153,458,305,457,152,152,152,455,303,151,151,151,151,301,301,150,150,150,150,299,299,149,149,149,149,297,445,148,148,148,443,295,442,147,147,147,147,293,293,146,146,146,146,291,291,581,145,145,145,289,289,433,144,144,144,431,287,430,143,143,143,143,285,285,142,142,142,142,425,283,424,141,141,141,141,281,281,140,140,140,140,419,279,418,139,139,139,139,416,277,415,138,138,138,138,413,275,412,137,137,137,137,410,273,409,136,136,136,136,407,271,406,135,135,135,135,404,269,403,537,134,134,134,401,267,267,400,133,133,133,531,398,265,397,132,132,132,132,395,263,263,394,131,131,131,131,392,261,391,521,130,130,130,130,259,259,388,129,129,129,129,386,257,257,385,128,128,128,128,383,255,255,382,127,127,127,127,380,253,253,379,126,126,126,126,503,377,251,376,501,125,125,125,125,374,249,249,373,124,124,124,124,495,247,247,370,493,123,123,123,123,368,245,245,367,122,122,122,122,122,365,243,243,364,121,121,121,121,483,362,241,241,361,120,120,120,120,120,359,239,239,358,119,119,119,119,119,356,237,237,355,473,118,118,118,118,471,353,235,235,352,117,117,117,117,117,350,233,233,349,465,116,116,116,116,463,347,231,231,346,461,115,115,115,115,459,344,229,229,343,457,114,114,114,114,455,341,227,227,340,453,113,113,113,113,451,338,225,225,337,337,112,112,112,112,112,335,558,223,223,334,445,111,111,111,111,443,332,221,221,552,331,110,110,110,110,110,439,329,219,219,328,328,109,109,109,109,109,435,326,217,217,325,325,541,108,108,108,108,431,323,215,215,537,322,429,107,107,107,107,534,320,320,213,213,319,425,106,106,106,106,106,423,317,211,211,211,316,421,105,105,105,105,105,419,314,209,209,209,313,417,104,104,104,104,104,415,311,207,207,207,310,413,103,103,103,103,103,411,308,513,205,205,307,307,102,102,102,102,102,102,407,305,203,203,203,304,405,101,101,101,101,101,504,403,302,201,201,201,301,401,100,100,100,100,100,499,399,299,199,199,199,298,397,496,99,99,99,99,99,395,296,493,197,197,295,295,393,98,98,98,98,98,489,293,293,195,195,195,292,292,486,97,97,97,97,97,97,290,290,193,193,193,289,289,481,96,96,96,96,96,479,383,287,191,191,191,286,286,381,95,95,95,95,95,95,379,284,473,189,189,472,283,377,471,94,94,94,94,94,469,375,281,468,187,187,467,280,373,466,93,93,93,93,93,464,371,278,463,185,185,462,277,646,92,92,92,92,92,92,92,367,275,275,183,183,183,457,274,365,456,91,91,91,91,91,91,363,272,272,181,181,181,271,271,361,451,90,90,90,90,90,90,359,269,269,179,179,179,447,268,357,446,89,89,89,89,89,89,444,355,266,443,177,177,177,265,265,353,441,88,88,88,88,88,527,351,614,263,438,175,175,175,262,262,349,436,87,87,87,87,87,87,434,347,260,433,173,173,173,432,259,345,431,86,86,86,86,86,86,86,343,257,257,428,171,171,598,256,256,341,426,85,85,85,85,85,85,85,339,254,254,423,169,169,169,422,253,337,337,505,84,84,84,84,84,84,419,335,251,251,167,167,167,417,250,250,333,416,83,83,83,83,83,83,497,414,331,248,248,165,165,165,165,247,247,329,411,493,82,82,82,82,82,82,409,327,245,245,408,163,163,163,407,244,244,325,406,81,81,81,81,81,81,81,404,323,242,242,403,161,161,161,402,241,241,321,401,80,80,80,80,80,80,80,399,319,558,239,398,159,159,159,159,635,238,555,317,396,79,79,79,79,79,79,79,394,315,236,236,393,157,157,157,549,235,235,548,313,391,78,78,78,78,78,78,78,78,311,311,233,233,388,155,155,155,387,232,232,309,309,77,77,77,77,77,77,77,77,384,307,307,230,230,383,153,153,153,382,229,229,534,305,381,76,76,76,76,76,76,76,455,379,303,227,227,227,529,151,151,151,377,226,226,301,301,376,526,75,75,75,75,75,75,75,374,299,523,224,224,373,149,149,149,372,595,223,223,297,371,445,74,74,74,74,74,74,74,443,369,295,221,221,589,368,147,147,147,367,587,220,220,293,366,439,73,73,73,73,73,73,73,73,364,291,291,218,218,363,145,145,145,145,362,217,217,506,289,361,433,72,72,72,72,72,72,72,72,359,287,287,215,215,358,501,143,143,143,357,571,214,214,285,285,356,71,71,71,71,71,71,71,71,425,354,283,283,212,212,353,494,141,141,141,493,352,211,211,281,281,351,421,70,70,70,70,70,70,70,489,419,349,279,488,209,209,348,139,139,139,139,347,555,208,208,277,277,346,415,69,69,69,69,69,69,69,69,413,344,275,275,206,206,343,480,137,137,137,137,342,205,205,205,273,614,341,68,68,68,68,68,68,68,68,68,407,339,271,271,203,203,541,338,135,135,135,135,337,337,202,202,269,269,336,403,470,67,67,67,67,67,67,67,67,401,334,267,267,200,200,533,333,133,133,133,133,465,332,199,199,464,265,596,331,397,66,66,66,66,66,66,66,66,461,395,329,263,263,197,197,525,328,131,131,131,131,458,327,196,196,196,261,261,326,391,456,65,65,65,65,65,65,65,65,65,324,324,259,453,194,194,517,323,129,129,129,129,451,322,193,193,193,257,257,321,321,449,64,64,64,64};

int s[V3];

int _inv(int x)
{
	int a=tab1[x/V1];
	x=(ll)x*a%P;
	if(x>P2)x=P-x,a=P-a;
	int b=tab2[x/V2];
	x=(ll)x*b%P;
	a=(ll)a*b%P;
	if(x>P2)x=P-x,a=P-a;
	//assert(x<V3);
	return (ll)s[x]*a%P;
}

int inv(int x)
{
	if(x>P2)return P-_inv(P-x);
	return _inv(x);
}

void init(int _)
{
	s[1]=1;
	for(int i=2;i<VX;i++)s[i]=ll(P-P/i)*s[P%i]%P;
	for(int i=VX,j=P/VX,k=i*j;i<V3;i++)
	{
		while(k>P)k-=i,j--;
		s[i]=ll(P-j)*s[P-k]%P;
		k+=j;
	}
}