n=10000;
h=[799,103,129,391,924,738,527,63,289,320,184,51,431,818,708,322,583,569,956,96,187,162,530,420,204,537,6,10,631,515,387,972,235,559,672,969,595,948,554,934,999,336,537,752,588,546,760,312,976,753,377,816,150,449,570,658,406,794,793,371,651,287,308,420,200,826,952,802,811,592,765,798,681,551,260,912,72,535,242,161,516,459,859,309,749,985,963,991,721,215,537,671,411,556,40,832,354,804,929,197,708,980,297,128,885,696,167,582,913,465,74,610,909,534,262,315,11,291,267,158,438,380,634,210,612,951,660,994,248,429,163,257,882,739,961,710,637,819,910,757,967,704,225,383,605,437,37,139,852,310,397,624,316,500,4,942,805,150,298,168,477,390,90,716,775,929,406,326,372,968,301,122,528,984,34,642,308,960,47,257,714,306,536,393,271,933,558,914,489,206,394,616,701,201,843,783,734,7,135,188,119,302,369,830,146,512,898,958,251,628,258,613,152,851,280,84,861,626,59,330,423,60,762,642,95,391,970,503,563,608,218,608,799,396,706,772,785,284,728,379,778,65,16,305,554,364,815,753,199,894,375,396,947,345,266,411,212,114,445,823,26,939,736,577,217,191,605,782,101,405,390,964,324,165,287,17,781,419,428,393,426,573,313,644,817,894,989,701,395,950,598,5,885,154,973,98,612,107,723,445,966,446,909,387,236,979,463,376,551,544,191,899,561,131,586,167,953,757,364,726,871,831,91,777,528,567,532,428,585,665,22,483,240,618,569,748,743,603,200,535,351,887,130,844,837,201,423,545,222,302,527,56,558,447,49,718,135,750,117,252,262,234,6,431,574,339,555,414,816,302,45,494,944,28,737,593,539,567,268,562,856,156,708,638,905,794,812,140,522,493,861,770,826,805,749,18,470,131,991,14,111,20,919,408,145,753,409,987,432,175,728,531,189,158,89,783,34,762,562,568,132,317,517,931,933,748,325,977,2,882,796,335,753,538,102,58,235,953,691,653,849,914,872,185,675,779,589,965,343,664,794,313,357,58,432,152,653,164,809,146,876,333,50,373,612,597,518,708,293,198,821,166,504,465,465,684,332,805,387,805,691,496,322,738,691,510,943,166,490,893,172,996,802,261,609,127,709,818,873,94,554,21,451,156,357,879,212,437,598,759,402,203,319,149,273,896,52,453,644,920,95,875,19,47,645,985,85,904,804,680,190,525,564,256,25,88,283,940,240,971,558,739,552,203,823,40,934,676,47,463,357,615,701,950,897,933,429,926,439,863,603,490,69,892,980,370,197,495,454,809,52,917,179,751,596,171,752,487,481,181,111,12,206,463,66,328,722,437,907,805,491,840,710,400,586,347,349,734,360,892,481,211,84,586,592,362,293,947,657,375,369,829,753,675,374,91,431,160,152,767,948,421,264,887,37,357,977,895,750,342,592,327,227,882,47,920,232,360,720,631,825,390,293,455,722,924,986,22,286,658,682,25,791,25,88,999,566,731,471,155,624,768,646,16,392,346,124,914,606,533,478,645,489,1000,970,905,44,488,331,676,286,970,546,945,82,305,994,331,43,456,623,288,574,120,971,528,906,75,963,310,415,351,64,509,251,95,49,12,218,951,803,45,666,100,239,100,954,674,214,143,503,115,348,976,622,281,588,388,466,118,702,730,370,388,502,268,766,829,502,88,425,775,470,868,29,723,735,70,852,657,825,223,804,494,86,158,530,781,418,959,938,730,986,694,437,64,182,665,635,45,879,188,634,119,569,400,500,525,523,268,480,247,529,670,706,795,556,831,5,611,323,925,930,123,846,573,857,690,392,742,92,53,150,201,445,607,390,483,373,708,373,588,442,236,777,269,606,178,241,154,966,352,693,807,617,876,927,44,486,845,474,442,159,167,75,227,517,507,480,534,502,11,357,819,338,882,8,232,152,6,752,12,324,525,873,288,497,135,103,374,881,361,810,190,651,696,307,157,186,18,753,600,813,476,604,744,300,917,143,343,213,15,791,566,792,440,879,890,547,58,551,548,271,136,115,768,118,639,606,199,842,878,181,467,326,688,869,41,612,812,570,755,233,304,121,809,502,625,213,448,198,750,35,362,679,584,884,488,421,995,579,90,619,660,476,719,906,847,281,872,348,460,473,467,231,605,184,793,150,808,108,595,911,521,782,914,606,284,817,294,5,652,611,349,111,257,606,185,841,267,553,963,166,379,28,474,815,393,321,355,401,252,319,168,745,631,504,888,227,650,687,185,791,610,45,557,560,669,909,74,305,371,547,577,825,255,214,403,953,292,238,595,906,534,873,379,48,235,804,276,148,48,401,949,269,384,216,967,140,97,774,283,384,832,21,289,607,876,205,889,611,827,117,568,636,16,322,374,632,594,224,760,867,688,305,207,49,612,939,470,560,698,963,437,676,756,949,413,697,863,341,607,716,681,244,792,716,328,101,946,673,489,162,551,453,38,418,434,469,764,920,858,636,943,396,214,361,244,931,208,224,533,437,659,651,268,851,845,381,414,559,771,887,83,8,64,462,674,871,363,334,300,709,812,857,670,460,352,987,555,515,252,366,200,987,675,388,588,908,724,975,586,818,905,342,629,891,292,863,750,630,782,96,386,861,375,257,774,604,215,263,901,621,539,96,225,119,19,849,268,177,631,248,52,270,968,849,650,621,450,363,687,247,578,721,855,704,761,482,141,795,323,789,695,59,383,910,30,860,59,581,250,946,725,810,126,150,963,756,413,328,215,85,527,115,540,497,179,56,965,192,668,954,991,275,774,859,462,352,714,493,50,657,690,864,533,632,959,697,199,607,222,984,583,6,487,412,402,921,356,152,451,457,80,149,690,849,353,611,670,610,962,92,887,471,484,748,151,256,654,923,572,1,78,291,920,46,660,323,636,488,11,222,276,621,699,731,258,956,106,455,581,341,76,630,250,254,41,250,839,817,630,911,281,969,241,172,221,853,683,496,129,539,91,292,594,18,625,921,428,878,611,92,878,928,224,552,347,933,204,657,227,758,461,735,330,263,287,807,275,609,648,854,407,989,539,859,820,886,693,801,461,62,762,861,981,875,23,616,701,44,764,729,684,414,829,417,448,539,525,534,657,73,36,681,45,758,34,575,263,827,5,553,37,216,22,313,247,565,847,793,254,988,182,282,307,547,889,297,374,770,482,110,152,696,96,56,564,763,785,308,245,541,36,832,892,360,290,312,46,818,951,1,216,257,359,595,514,709,743,237,419,610,311,564,758,704,45,473,385,763,316,184,545,163,250,709,753,202,139,725,428,75,17,683,528,402,655,327,196,973,701,427,101,925,60,652,260,546,505,425,137,98,521,226,372,665,229,999,570,452,620,465,289,939,413,969,451,184,432,395,87,204,554,37,370,366,782,29,500,606,582,627,603,265,440,513,618,489,967,303,655,503,778,300,194,274,181,616,565,889,800,350,610,899,768,304,745,220,259,980,624,443,745,309,676,289,500,114,70,761,141,122,107,52,193,36,357,631,799,913,175,165,327,425,806,450,870,465,65,96,860,4,112,550,253,965,824,606,273,217,932,977,232,262,86,820,647,223,511,819,262,305,598,941,279,745,677,92,58,16,961,482,631,969,378,0,467,200,100,880,229,157,521,428,647,805,583,188,563,727,70,24,405,654,778,23,333,231,111,263,922,714,850,298,676,837,261,398,602,507,973,231,51,168,462,503,494,504,283,394,408,837,774,212,332,615,657,431,800,695,848,730,976,474,252,518,463,584,283,347,862,338,805,377,681,853,437,855,978,441,495,619,812,728,299,621,833,686,75,724,158,264,721,303,849,961,273,951,940,602,705,74,190,186,705,702,800,446,549,244,249,797,60,144,239,640,277,428,109,788,453,650,290,594,566,953,905,607,275,41,573,859,158,31,218,701,665,701,142,281,949,14,49,588,816,528,961,64,69,234,632,248,677,978,883,761,705,384,37,497,835,128,311,906,264,709,781,912,524,980,708,282,901,392,952,368,918,786,331,975,150,752,980,158,326,95,928,892,969,360,720,283,691,656,513,448,499,557,191,469,539,34,277,364,241,721,162,265,204,364,828,709,669,949,203,317,552,79,795,61,306,323,50,719,991,13,500,720,433,803,290,660,976,625,375,289,654,652,96,725,516,235,128,78,468,215,661,440,935,901,639,243,79,346,497,257,416,971,365,272,279,898,967,458,354,246,946,707,289,948,652,451,689,156,915,266,278,47,44,759,891,369,558,933,971,89,960,182,70,431,321,761,613,752,61,723,830,239,198,961,302,525,712,421,353,628,182,665,787,101,916,556,624,985,286,837,188,943,529,882,849,163,572,519,530,131,308,849,189,365,811,965,323,354,860,120,557,192,560,503,142,771,232,19,552,558,768,185,724,613,107,63,794,873,329,153,136,948,967,652,741,8,148,799,86,988,405,369,665,352,309,863,395,231,772,800,255,59,2,216,740,170,895,912,221,373,531,108,535,232,241,413,698,885,580,486,272,177,976,875,572,972,376,546,442,194,480,915,993,301,87,270,434,595,256,448,550,788,810,349,831,631,393,156,899,380,470,571,191,587,144,501,796,915,909,10,693,417,776,80,281,937,869,525,920,377,774,748,145,92,214,696,590,13,581,222,71,363,651,656,316,76,70,955,549,628,959,110,671,138,445,581,601,997,445,269,658,540,859,673,264,96,847,269,28,878,58,213,479,66,288,241,590,826,906,571,296,236,261,877,329,742,485,331,783,703,439,572,967,266,511,833,589,352,174,204,559,139,301,516,13,249,841,615,641,180,861,962,987,78,131,272,23,151,574,194,37,299,326,568,418,578,832,89,487,90,145,305,21,134,990,844,40,143,893,952,890,209,193,85,511,390,455,535,596,175,553,306,886,697,685,280,640,657,977,986,743,19,809,709,47,733,62,7,606,617,857,490,641,147,846,26,812,773,441,3,150,892,209,686,382,921,84,888,160,210,518,342,402,59,105,643,788,852,154,449,133,57,98,933,424,174,187,963,831,618,351,488,472,220,10,984,778,256,474,569,812,472,404,74,468,808,509,84,610,458,625,982,191,334,251,886,920,371,51,970,994,579,286,18,768,444,693,967,553,310,848,350,71,832,944,518,670,766,542,469,509,210,845,471,308,259,305,267,282,917,386,280,443,311,504,32,822,585,305,602,540,677,779,361,35,369,86,810,107,952,989,880,6,393,17,149,426,275,842,570,348,936,555,549,30,416,482,395,738,620,208,593,948,807,166,675,388,682,718,593,260,549,899,438,208,819,513,464,859,195,749,449,381,718,397,67,429,712,575,552,249,930,405,920,298,406,791,311,71,950,99,211,117,894,374,699,637,932,581,66,549,198,916,618,636,389,540,850,4,578,52,104,932,19,678,335,535,970,594,829,452,462,227,904,518,123,839,472,287,965,702,825,916,206,606,826,428,393,247,188,759,628,380,711,627,647,448,491,395,673,843,872,629,981,207,367,91,883,593,623,681,311,815,285,481,397,555,266,388,390,38,738,840,933,79,442,484,205,813,155,454,761,949,578,238,367,454,110,943,826,222,337,659,257,393,735,133,3,651,3,140,871,279,569,667,775,519,112,818,660,930,714,21,144,176,433,688,10,280,251,906,37,932,995,163,663,8,671,191,365,47,856,49,67,386,499,79,555,535,58,841,512,160,294,410,585,361,263,240,837,786,79,930,60,559,1000,144,29,400,10,702,88,479,637,116,853,726,708,499,444,653,834,647,677,458,768,883,316,766,290,899,653,972,357,689,917,835,999,484,909,507,250,449,241,211,261,19,770,928,270,496,156,708,616,495,127,389,573,482,885,224,121,970,637,940,683,133,212,974,755,663,161,324,787,10,11,284,383,916,845,144,683,914,396,334,377,73,358,531,470,479,216,582,882,926,927,1000,660,626,548,493,290,513,177,541,948,911,784,752,606,58,310,269,756,478,767,523,985,377,762,621,697,597,586,517,758,74,743,833,155,899,418,336,260,610,89,728,85,300,429,714,8,294,238,721,677,566,394,850,927,454,96,706,375,153,603,603,611,683,224,750,399,3,111,769,528,585,708,669,947,389,441,487,345,457,818,753,94,214,990,740,446,983,491,308,428,298,394,784,674,795,814,808,944,885,548,256,280,169,164,734,37,645,898,223,274,75,274,734,86,536,570,548,405,858,549,109,195,877,349,110,762,462,897,942,178,959,480,110,897,570,158,548,797,386,507,815,710,613,532,717,571,942,428,14,561,867,400,633,7,621,810,319,55,52,712,362,605,483,674,229,517,472,933,104,620,815,22,993,260,331,344,695,466,904,845,981,732,794,692,609,107,575,480,457,47,507,491,225,501,934,993,129,161,132,923,514,789,560,946,177,466,177,529,877,161,209,111,855,566,52,928,672,986,690,811,45,294,665,626,633,158,618,510,755,376,702,369,86,122,936,405,366,308,460,844,837,838,904,666,744,720,66,182,393,776,746,23,504,707,733,931,739,176,116,517,423,555,923,239,602,320,412,690,767,63,705,945,47,467,936,643,594,692,676,2,719,389,429,207,248,731,548,266,116,846,53,86,968,669,680,243,693,251,350,657,104,811,221,165,502,178,462,481,928,979,658,413,958,804,205,583,541,233,584,79,186,974,899,82,544,423,340,502,256,256,912,123,916,521,65,431,410,994,628,361,422,970,71,123,115,614,495,976,747,131,257,709,312,268,495,4,102,51,319,992,751,408,249,954,398,481,281,76,608,197,967,631,77,740,121,890,440,4,454,451,649,976,40,756,387,493,939,873,1000,841,565,369,712,889,667,120,286,133,814,918,571,342,204,936,98,319,485,578,94,526,812,300,407,417,241,774,827,247,22,870,449,711,757,74,177,33,648,171,844,557,554,708,873,872,343,828,171,881,637,475,228,517,305,388,380,272,17,569,737,713,266,175,917,996,997,234,574,767,340,814,696,557,865,843,294,68,59,328,970,24,145,335,211,837,194,365,467,509,365,275,687,68,245,444,823,146,15,399,205,420,316,331,105,114,328,186,211,113,91,254,335,365,964,247,776,780,104,312,132,362,179,963,945,762,433,490,899,808,976,226,607,339,474,277,697,506,198,820,31,615,850,98,478,755,402,854,126,522,562,304,635,483,345,605,235,708,714,862,777,855,917,846,817,542,18,199,889,75,741,282,438,381,181,516,814,962,348,289,262,351,242,782,503,3,285,279,825,88,672,529,977,778,631,959,416,265,576,805,997,1000,260,603,589,382,234,4,442,321,170,572,705,868,310,770,571,105,624,738,234,82,928,307,865,182,534,696,664,531,725,907,593,359,550,542,374,483,539,375,733,434,389,151,767,360,487,399,418,545,517,228,935,823,329,633,754,248,413,870,501,572,408,845,994,442,338,225,421,656,241,75,522,851,56,575,605,165,92,211,829,32,493,708,26,382,231,117,637,470,999,455,244,408,515,690,33,262,467,942,833,345,817,967,960,279,802,336,582,991,229,240,962,171,383,939,85,520,108,624,357,875,767,43,151,809,943,155,658,535,38,80,289,147,158,760,897,323,458,144,434,811,416,608,697,450,556,267,794,944,330,432,332,955,759,140,10,841,734,99,810,67,942,138,576,147,786,318,843,1000,29,707,48,10,549,973,781,583,689,707,306,888,731,201,294,842,982,403,447,689,257,501,808,309,916,878,219,97,219,396,648,601,556,469,793,670,199,612,675,14,258,185,143,744,569,165,81,662,636,742,144,112,351,747,958,804,947,370,212,442,991,342,88,359,835,33,510,178,527,980,222,923,679,134,622,481,319,188,272,653,773,968,994,923,854,124,311,575,885,960,291,998,143,699,749,664,750,368,186,189,257,357,632,66,581,746,153,72,557,609,859,407,123,56,989,406,182,808,389,548,354,297,767,364,937,760,830,326,616,864,38,468,396,400,213,735,798,408,1,10,380,453,999,383,740,85,710,641,656,570,825,946,345,300,531,933,525,695,911,639,955,125,60,345,670,763,961,217,857,563,114,901,580,794,59,907,197,73,150,382,101,423,453,221,233,466,738,465,13,954,302,39,817,700,933,328,502,837,402,582,651,392,693,79,989,495,981,688,17,570,201,289,368,816,326,25,697,28,435,506,240,298,791,712,306,400,177,798,781,698,637,433,486,919,526,520,291,476,548,177,41,703,547,487,78,400,170,746,673,698,623,192,832,120,796,47,890,673,107,888,396,630,134,479,682,325,662,346,273,337,235,865,211,394,813,685,602,45,678,361,480,914,458,222,309,383,257,804,92,694,194,464,717,925,369,480,75,52,730,797,883,576,830,935,522,821,522,433,929,874,890,150,9,649,404,204,204,962,126,689,698,911,171,860,105,337,965,989,292,129,357,259,110,7,851,989,185,373,724,964,9,863,542,719,940,767,936,418,134,928,657,836,339,982,980,159,667,893,240,389,332,624,753,707,588,337,349,835,352,28,946,614,997,716,788,563,111,134,469,574,367,299,581,841,957,291,41,748,26,297,974,920,241,671,700,213,733,221,218,450,920,590,544,145,834,31,471,864,786,879,635,489,158,631,904,308,336,231,300,175,601,890,536,391,283,24,938,646,803,677,186,645,88,932,471,897,517,842,55,855,380,863,425,233,400,942,243,50,264,252,752,45,970,958,655,666,664,872,137,234,848,51,96,282,174,438,459,363,727,950,172,558,622,482,895,146,460,316,77,984,845,527,338,643,864,261,229,724,642,759,201,686,866,45,786,704,644,977,551,993,460,278,343,680,620,601,881,886,228,979,665,502,183,770,372,572,438,769,620,50,895,235,594,875,908,211,832,825,394,466,278,172,771,536,728,508,3,190,166,101,383,323,261,943,792,263,326,273,534,293,454,836,744,692,261,177,282,44,337,139,420,930,948,33,281,5,370,541,604,900,751,714,397,637,553,699,202,611,776,615,933,804,311,938,443,361,249,999,884,304,86,468,979,22,137,123,779,710,5,429,691,603,682,64,900,944,58,261,674,96,400,197,584,906,710,384,409,480,240,252,287,174,600,512,911,922,843,309,794,411,51,515,249,105,909,224,940,367,39,134,411,58,306,199,533,886,810,351,960,437,183,9,857,940,774,245,423,811,113,242,362,604,243,87,864,643,1000,743,37,937,390,390,936,892,169,281,777,392,866,290,822,783,385,510,851,989,547,478,201,28,895,636,543,630,732,896,689,394,322,332,246,778,628,156,143,198,724,252,210,242,986,217,579,591,686,877,324,295,395,76,547,650,971,611,645,512,727,448,296,439,351,537,507,176,861,456,448,682,491,346,353,512,159,475,802,995,83,663,427,514,994,849,521,806,130,195,880,954,436,340,685,377,128,118,132,575,450,106,271,372,372,373,727,169,810,33,855,909,836,361,523,510,348,927,220,463,844,991,816,398,539,14,374,650,659,313,649,576,285,755,609,596,141,413,122,292,722,860,155,197,206,106,877,936,604,811,956,332,842,384,142,613,135,660,210,340,935,611,523,260,632,904,929,914,168,540,744,114,99,189,549,622,926,861,957,77,920,519,778,379,703,512,692,85,122,972,497,889,636,673,122,384,11,627,754,28,978,303,273,712,151,365,390,360,253,287,654,12,819,128,844,580,842,21,727,319,601,512,450,631,394,203,337,546,153,206,715,858,986,197,497,681,407,247,105,175,186,349,281,871,348,83,780,902,573,570,506,22,985,350,375,64,778,541,426,720,688,935,863,216,293,773,358,315,906,177,267,38,986,336,148,617,457,879,161,209,157,865,603,633,903,455,380,952,583,343,126,34,986,779,609,332,900,897,64,897,20,597,504,867,72,585,465,69,30,540,90,579,63,768,495,283,988,115,347,526,274,945,222,406,36,658,587,974,120,172,30,501,5,688,77,418,856,494,601,774,489,563,247,612,551,470,490,206,495,882,230,233,323,317,233,647,836,964,373,104,203,666,947,522,285,581,770,295,919,763,699,812,409,392,580,385,89,35,266,581,684,616,969,461,622,168,635,783,859,188,854,539,421,729,480,877,269,928,263,364,516,97,821,510,49,367,658,183,365,123,513,64,293,133,348,597,428,945,894,205,210,415,451,195,239,163,695,850,646,434,347,383,649,528,483,326,301,980,693,243,421,283,217,99,0,346,264,359,266,771,537,877,37,27,844,306,757,212,787,201,986,127,542,956,839,122,107,540,799,838,416,5,627,802,222,234,488,710,341,974,240,93,32,673,974,55,242,107,661,102,71,483,234,28,526,261,556,704,631,907,634,803,880,282,923,489,0,177,115,182,524,990,397,36,481,557,855,44,7,250,627,915,920,188,389,634,246,855,166,810,320,829,756,956,924,784,834,634,492,586,256,423,968,490,471,157,39,875,677,652,506,499,919,347,267,605,287,334,176,432,716,154,224,531,475,49,114,851,674,628,433,638,956,406,883,118,776,787,811,7,914,478,681,292,477,746,380,493,33,207,467,766,571,26,386,933,161,161,984,129,438,913,292,882,947,834,48,116,353,900,841,37,717,543,534,498,195,30,724,401,467,804,167,554,312,122,121,8,126,530,738,387,15,146,859,555,118,732,255,611,53,778,495,412,827,138,371,827,966,794,983,91,317,930,695,193,350,372,959,302,99,436,107,643,357,769,283,411,315,69,78,781,185,401,934,832,332,232,615,610,254,597,313,849,952,982,365,756,686,473,573,52,921,9,724,660,241,859,511,112,112,288,196,861,685,95,145,639,505,476,259,402,274,33,336,168,210,877,643,529,421,824,227,804,430,326,53,933,353,334,384,782,976,579,876,450,663,842,134,65,655,529,774,963,597,24,477,602,558,165,374,430,710,917,598,266,255,566,568,378,427,374,847,443,798,900,686,210,276,340,311,872,987,147,370,683,9,221,992,327,892,79,867,12,390,512,898,92,868,333,798,441,614,473,255,754,840,910,202,210,879,618,833,606,812,885,254,323,90,862,509,948,102,10,594,82,618,56,117,413,632,229,780,464,227,662,194,311,102,583,795,950,163,645,647,560,869,654,575,903,671,178,183,488,399,769,127,193,492,258,49,147,650,172,149,203,56,743,867,509,208,358,928,188,330,22,799,749,44,537,18,868,813,512,276,497,669,592,940,841,280,396,900,363,654,655,694,468,887,168,10,55,49,679,921,1,271,985,922,886,969,446,426,143,975,300,520,627,438,291,978,153,127,709,712,621,482,126,724,972,398,694,92,763,41,734,24,464,405,869,797,96,217,89,155,583,527,885,541,272,14,258,75,628,616,804,225,409,558,185,761,208,795,979,793,654,876,62,825,495,626,225,527,718,685,225,840,580,993,924,974,929,452,988,179,972,264,324,15,912,874,489,330,626,181,354,373,697,484,539,100,855,821,920,423,987,992,936,264,112,949,803,914,302,221,32,762,838,230,144,20,309,161,56,955,608,557,115,358,445,869,657,642,669,569,343,807,821,878,713,60,936,492,24,468,733,950,514,866,778,930,441,615,675,685,653,364,603,653,647,54,26,871,805,178,911,759,992,240,450,919,369,324,71,886,240,416,190,261,779,758,179,202,709,628,828,597,718,35,951,518,24,359,38,691,427,346,20,865,785,465,482,791,559,159,649,76,999,393,751,946,56,747,389,886,80,855,732,470,223,9,989,251,800,744,824,281,182,79,24,143,794,109,199,443,938,252,7,372,956,495,119,2,901,304,840,244,895,549,833,992,563,28,320,858,100,568,877,314,985,13,685,804,100,959,466,661,581,644,960,823,873,93,903,949,852,584,39,585,593,395,313,1000,702,87,174,643,479,147,539,741,597,298,809,890,774,485,572,756,408,337,424,743,452,282,540,100,837,321,530,748,831,332,773,588,196,333,685,766,902,954,989,26,405,618,630,88,581,101,957,512,493,10,840,448,352,383,902,667,505,355,549,680,581,626,601,498,745,982,239,60,235,610,620,595,545,969,549,25,593,227,173,33,229,714,449,451,178,653,900,115,410,47,62,6,966,324,567,248,589,975,709,158,448,905,28,645,984,29,469,703,624,702,86,689,108,233,898,24,368,189,87,496,938,926,729,778,754,737,684,736,539,888,739,266,516,837,404,395,374,802,637,3,431,682,140,941,950,90,478,995,263,200,802,858,485,88,360,200,694,648,82,900,613,242,625,907,561,458,504,987,3,274,66,563,94,532,356,370,663,544,423,474,147,55,487,409,387,637,399,486,869,117,527,687,423,880,749,22,715,812,452,902,578,291,313,792,685,772,123,868,488,545,278,401,155,380,429,195,775,624,448,834,461,869,350,830,614,161,407,510,680,1,489,340,385,485,236,165,549,561,51,218,26,980,384,90,195,171,389,114,192,887,793,986,651,162,267,902,635,353,826,46,279,976,475,143,924,368,499,947,802,262,996,683,878,896,397,11,984,273,497,791,563,789,198,774,245,738,502,481,822,21,294,309,53,882,903,521,579,262,590,494,899,287,357,470,436,346,601,105,223,617,558,853,540,120,730,91,482,167,665,89,360,117,465,461,340,563,910,726,68,792,60,967,440,749,889,47,192,432,391,324,726,2,78,771,253,137,790,832,330,553,928,465,4,693,99,333,747,647,988,657,351,56,618,250,604,373,302,730,968,359,259,391,988,626,708,752,932,99,867,204,919,998,902,20,255,368,378,293,875,183,106,730,351,586,235,612,519,266,724,90,935,178,72,366,511,914,732,532,549,164,567,146,9,551,605,385,818,620,907,187,956,644,553,571,247,687,773,993,156,582,755,917,652,729,224,709,419,280,646,210,178,221,598,712,466,992,802,765,661,599,66,525,327,652,141,597,119,778,100,652,542,49,368,363,291,6,944,481,52,932,530,519,480,426,613,684,943,325,137,368,446,938,154,997,751,260,893,545,300,68,874,953,376,618,899,745,35,743,154,403,694,394,616,934,576,933,318,66,881,390,330,247,189,521,926,124,249,203,41,676,869,30,742,843,686,599,585,107,807,95,930,694,214,557,453,658,437,947,947,1,465,707,554,186,548,561,456,270,479,423,875,822,850,917,469,266,551,92,918,922,679,7,288,500,788,732,537,585,671,682,154,185,874,222,308,286,805,738,612,273,197,763,96,303,947,258,706,217,198,147,134,452,779,109,364,83,974,228,419,921,137,125,756,23,290,819,348,282,463,154,205,979,747,476,683,373,868,360,953,904,126,710,681,529,974,77,175,387,257,263,594,608,649,334,721,676,422,664,546,745,804,806,837,689,37,985,914,667,847,488,388,163,518,201,418,949,126,963,435,97,933,931,31,175,706,988,859,84,76,587,78,97,692,323,266,146,994,388,656,752,223,476,828,155,498,769,105,856,996,869,317,892,704,648,72,347,276,341,722,881,655,589,22,864,313,593,205,604,747,684,253,104,652,853,761,502,357,570,86,149,397,372,115,922,330,260,2,549,595,448,696,109,117,137,928,826,267,402,827,538,152,661,352,775,310,191,113,944,222,816,15,136,511,624,689,555,207,652,318,142,474,410,129,717,284,232,920,352,519,700,53,516,344,205,297,71,123,644,594,628,538,23,858,341,888,937,65,54,144,560,834,548,194,171,990,388,963,393,236,18,154,636,15,494,133,953,110,465,423,422,798,872,165,981,795,240,705,679,949,96,110,509,464,180,208,567,293,166,176,990,688,135,872,578,105,982,652,364,761,903,761,150,170,95,970,953,644,718,672,636,943,523,129,20,812,146,221,917,804,1000,528,120,717,434,383,49,916,514,603,655,114,324,689,193,945,972,613,821,427,404,125,13,910,277,648,615,430,172,465,948,918,351,462,625,509,548,499,199,953,924,536,240,826,678,751,396,147,764,584,170,270,140,724,333,455,90,108,768,230,521,65,711,862,126,741,132,818,258,612,978,497,733,736,956,342,485,132,14,748,630,120,204,671,290,648,544,547,330,376,734,818,246,681,310,504,255,808,218,142,515,850,907,210,150,864,753,943,267,65,673,611,34,403,442,125,741,757,797,683,678,946,409,162,864,385,217,182,845,626,511,613,940,761,510,843,805,200,201,603,921,415,426,440,140,401,204,129,813,923,933,833,391,632,945,341,691,306,476,182,420,14,740,728,481,736,517,476,487,454,563,713,15,996,850,262,95,136,273,341,73,429,154,444,468,509,231,323,462,629,822,268,293,736,644,661,450,750,562,236,25,281,250,610,917,564,92,311,109,4,326,677,846,877,95,956,585,656,219,184,11,107,358,722,408,388,534,757,216,769,793,785,212,594,794,903,257,621,370,187,18,761,208,684,219,815,275,971,223,302,845,631,23,926,873,935,232,45,722,565,872,767,843,26,204,315,294,657,401,815,303,705,769,377,333,72,884,270,167,199,422,844,792,687,336,896,202,720,291,575,100,945,475,289,21,153,308,730,481,798,28,909,106,42,727,298,172,705,886,261,871,399,132,509,482,218,945,254,446,154,896,736,31,244,492,467,67,181,947,652,722,502,817,243,819,593,257,760,42,763,8,75,173,648,871,377,962,986,218,702,660,365,257,816,569,318,763,689,760,507,537,103,14,164,506,471,81,223,513,568,511,903,359,685,390,226,375,678,69,849,464,586,96,696,421,204,284,302,599,506,416,520,862,895,302,645,245,35,775,215,807,489,158,778,458,7,669,586,428,387,8,995,473,182,548,898,68,293,861,953,634,154,346,928,131,579,739,869,244,331,6,858,137,437,347,463,724,275,13,691,295,102,887,392,869,418,959,578,775,160,193,561,539,71,23,856,711,438,427,483,710,802,724,275,23,70,974,140,679,142,257,935,230,269,592,272,124,413,318,599,487,246,900,827,949,24,492,700,964,23,940,832,588,307,861,603,414,302,136,517,111,846,294,30,656,21,970,31,976,360,101,303,360,892,831,96,19,348,69,427,520,728,439,200,447,245,317,231,91,104,356,615,593,32,649,43,777,160,323,319,365,425,726,819,120,71,185,542,215,382,65,748,796,994,20,139,452,740,558,810,54,78,319,140,228,735,259,531,62,819,971,105,337,645,927,532,879,218,969,91,644,837,954,473,369,742,891,561,965,551,374,257,197,569,599,69,959,232,604,667,829,391,907,311,791,139,859,997,311,841,533,864,142,833,778,624,235,39,312,228,27,21,235,179,91,538,350,736,48,445,888,430,278,217,286,172,771,617,303,392,307,586,465,414,178,770,701,542,18,765,544,743,750,595,80,967,257,329,987,268,968,714,523,838,148,157,106,388,800,102,788,744,395,479,177,661,700,613,77,828,670,719,4,184,601,130,755,688,332,15,775,796,343,163,249,650,65,976,682,305,563,619,256,387,150,282,195,358,20,648,336,137,342,88,216,149,155,343,410,533,726,361,285,500,799,397,429,105,658,531,583,1000,475,345,229,190,407,123,198,5,22,218,676,647,501,50,597,348,411,775,149,947,120,753,96,771,445,544,162,431,32,538,971,64,268,305,760,175,743,282,976,843,238,501,149,543,991,262,250,325,728,716,653,415,253,111,309,527,377,470,348,442,70,17,416,372,573,789,420,415,418,420,941,303,190,416,221,426,542,592,14,166,214,981,392,131,856,772,80,424,170,775,79,321,410,147,653,362,277,128,154,356,274,877,38,626,398,407,165,107,889,425,147,358,446,326,885,426,869,130,402,63,566,853,570,87,43,638,414,485,280,509,173,971,991,249,219,465,383,706,335,718,555,629,382,244,624,828,132,745,507,737,432,307,28,194,444,138,71,403,280,918,943,58,730,226,770,37,311,531,303,441,784,224,856,281,192,897,15,669,345,585,23,394,536,603,763,91,385,119,178,839,84,102,892,538,726,516,667,948,689,366,791,849,976,757,942,138,44,925,507,128,301,444,837,295,606,657,35,622,281,588,779,548,615,908,752,703,40,807,728,790,762,366,255,949,920,707,862,858,148,395,254,135,57,821,104,193,790,19,785,327,81,512,243,706,926,829,687,265,574,336,900,381,164,766,593,662,234,360,560,565,81,917,990,598,238,470,982,799,462,134,168,396,990,282,140,336,848,944,212,716,956,600,757,531,421,692,852,117,708,529,932,233,943,561,715,337,208,896,831,816,772,336,921,791,530,505,574,680,753,375,910,32,228,307,871,527,836,536,605,751,179,342,127,150,728,828,316,739,387,59,174,111,611,128,931,594,751,879,807,701,420,783,296,550,127,109,352,707,573,846,961,913,703,194,145,437,963,894,214,33,456,725,273,236,189,582,140,564,491,800,625,633,65,662,688,606,757,449,768,359,938,702,911,301,477,523,826,916,63,418,877,95,885,918,22,946,711,354,344,247,169,979,496,816,204,719,820,331,904,89,543,292,983,541,348,209,400,251,638,444,400,422,195,728,722,762,994,321,541,361,107,672,940,746,628,115,97,557,527,752,140,155,618,745,285,445,796,286,621,979,998,308,13,560,431,855,173,546,24,433,417,258,226,856,800,504,752,819,61,354,963,354,360,993,935,840,311,116,147,240,618,938,799,539,959,854,585,75,450,979,116,517,596,701,109,667,589,582,875,368,776,981,25,591,560,195,809,550,798,215,815,309,277,575,140,677,704,698,279,203,125,766,470,283,390,917,864,652,666,849,399,416,291,875,496,167,51,372,25,794,56,336,536,351,118,649,498,906,985,533,671,262,460,770,668,484,901,625,539,839,775,276,597,463,915,379,847,845,568,541,56,596,134,352,518,27,249,343,972,669,897,439,911,906,500,279,703,518,19,416,760,510,589,360,937,162,490,993,547,64,267,43,844,713,771,598,125,462,300,888,765,733,711,63,580,363,983,264,519,513,379,317,372,424,212,383,779,486,168,997,276,589,301,6,861,168,112,147,724,627,894,149,563,480,363,279,832,509,380,434,956,805,496,720,311,397,799,214,281,190,530,627,138,859,32,664,310,36,636,821,48,806,78,938,255,518,484,423,400,992,792,915,905,892,110,807,472,925,612,982,807,988,882,112,818,900,408,722,247,714,495,50,405,764,168,650,102,602,228,620,13,200,263,45,785,692,898,388,540,926,695,23,777,790,647,645,197,734,636,678,874,165,895,78,638,257,588,567,573,75,118,421,413,112,959,901,961,65,751,962,876,99,997,153,288,413,714,80,757,278,289,33,714,208,252,821,848,204,695,976,352,431,572,957,591,744,548,505,849,97,880,339,950,59,721,335,448,668,237,968,275,819,950,648,345,917,199,193,349,207,118,640,484,118,112,351,753,492,86,410,764,540,540,701,231,297,502,338,249,366,56,443,227,646,80,491,868,47,574,330,981,25,857,738,74,632,894,155,689,481,148,634,594,573,573,705,562,677,13,235,219,379,909,572,501,937,152,217,17,205,742,35,472,683,960,925,327,92,283,82,499,316,260,572,233,807,552,157,571,328,889,995,34,461,98,69,202,188,850,489,316,834,165,339,399,256,630,221,31,852,118,92,707,914,466,979,254,47,6,406,459,271,332,956,538,527,787,377,852,371,644,847,499,429,115,994,183,500,136,970,554,503,128,952,941,505,976,780,130,952,291,96,496,533,712,826,405,189,810,518,917,827,107,264,822,857,636,765,613,444,728,505,411,331,952,840,461,589,679,309,545,279,886,310,37,927,231,520,635,460,217,250,34,151,604,503,440,298,40,781,940,263,674,749,80,996,575,253,895,717,522,537,171,686,679,119,980,788,414,807,123,262,425,709,349,217,505,476,36,42,485,851,62,39,332,722,240,628,422,532,658,485,769,644,539,242,401,445,161,982,735,383,228,91,13,222,551,355,12,631,30,788,488,530,28,211,862,766,96,503,591,171,68,26,144,973,856,449,1000,676,684,374,447,64,267,340,133,663,473,281,595,519,413,883,153,517,832,699,576,636,436,445,345,932,697,575,805,595,4,804,896,997,227,358,134,563,971,85,521,50,269,748,49,793,715,295,691,896,628,949,945,569,782,155,943,574,860,45,67,745,835,380,972,214,316,7,100,898,392,450,326,410,729,359,779,630,979,779,941,210,206,924,906,270,76,656,381,63,393,200,295,713,388,941,495,986,51,979,189,673,735,620,710,28,741,139,630,743,152,891,841,171,349,866,728,662,216,289,23,535,240,379,116,622,560,609,457,73,695,79,84,170,313,878,663,399,515,533,550,358,74,701,656,271,160,165,189,234,614,656,604,800,456,125,157,234,32,252,279,23,924,342,299,996,862,94,926,74,49,828,372,299,55,817,641,645,215,260,30,173,270,409,490,458,873,43,892,94,60,686,800,702,105,621,157,431,321,709,488,815,179,408,199,318,355,521,275,992,354,123,719,235,915,466,519,165,172,898,679,445,701,981,328,662,79,947,753,772,424,797,401,58,56,92,348,226,235,48,703,551,43,678,303,762,598,854,531,101,89,446,261,303,206,373,78,393,366,708,720,610,914,435,191,413,317,796,282,262,957,525,137,130,232,785,252,88,372,909,96,77,888,77,842,957,889,838,988,289,917,136,577,814,455,436,62,428,850,651,582,813,721,606,259,286,386,884,991,821,334,127,5,119,928,662,361,533,12,706,530,642,139,151,267,92,587,32,697,754,908,307,557,114,847,844,748,983,610,5,611,140,433,848,100,987,627,322,134,54,469,688,335,731,141,253,951,49,512,410,300,522,181,738,208,246,382,312,391,507,325,485,117,434,294,566,480,755,720,237,371,913,305,911,78,895,178,828,885,279,60,6,396,492,769,283,424,224,162,298,340,730,150,397,398,412,550,415,611,339,470,596,381,131,940,663,497,214,308,955,854,339,186,163,37,479,824,541,97,546,453,877,69,455,774,718,238,150,768,677,548,191,238,313,581,946,0,227,112,446,98,392,911,248,831,694,794,869,290,115,800,764,511,911,151,867,297,675,60,670,110,903,178,586,707,356,499,800,908,475,818,297,233,424,730,611,881,674,775,211,903,605,113,796,226,477,217,940,924,186,223,893,254,325,711,503,346,435,971,555,443,369,824,635,498,77,210,864,815,806,73,849,606,144,81,347,280,706,370,62,601,592,886,43,722,862,567,63,572,99,41,80,135,518,958,165,468,165,871,567,939,541,218,330,133,492,126,918,358,514,336,254,482,865,97,260,359,693,1,248,439,55,29,185,769,466,71,174,930,759,234,159,885,2,521,100,269,982,715,369,187,610,11,544,300,236,746,457,786,1,858,597,936,745,297,895,385,975,681,841,567,517,881,558,120,427,556,387,907,11,742,197,452,647,924,377,582,622,305,130,317,19,967,185,225,300,318,444,254,965,154,138,320,512,538,998,963,466,900,589,95,704,151,957,304,489,220,607,901,626,509,883,5,34,283,885,879,795,138,483,265,351,539,196,501,137,49,396,34,777,553,727,885,402,933,718,429,479,532,7,460,694,827,789,683,593,109,188,367,885,812,511,464,260,619,85,849,729,564,37,387,327,136,871,528,230,724,188,664,525,276,698,737,792,306,871,828,91,240,749,107,906,853,973,6,983,449,463,513,526,821,636,598,568,496,261,245,112,571,712,582,610,769,123,669,158,997,893,381,969,351,15,572,464,739,309,49,64,970,619,860,705,764,518,345,827,200,815,495,328,944,730,447,223,634,311,359,339,211,503,285,885,758,375,176,684,622,604,11,531,72,727,354,554,596,244,890,820,147,396,651,691,151,314,725,282,605,753,496,45,530,571,482,12,86,115,392,962,184,607,411,243,860,814,377,987,737,97,18,566,171,185,812,964,724,547,889,340,999,742,807,240,155,595,451,433,806,520,901,894,315,189,403,757,489,534,909,349,715,572,44,89,588,469,337,697,758,286,832,206,437,876,759,901,136,908,550,119,704,252,645,878,489,423,254,772,952,71,373,870,884,325,594,256,549,742,812,12,200,770,124,432,450,701,565,947,787,538,931,669,199,324,570,192,486,386,899,741,88,972,928,360,777,431,561,89,52,819,439,146,150,74,33,92,712,190,274,286,576,981,125,738,815,714,147,443,362,997,450,363,163,151,620,585,808,754,836,293,413,931,739,706,554,593,232,49,753,264,143,532,927,838,177,503,548,389,265,237,161,280,260,666,642,2,653,90,25,265,201,633,938,738,818,867,619,446,304,758,91,520,750,593,93,764,553,733,813,529,923,799,674,95,915,302,890,127,451,950,955,992,660,388,998,46,357,390,918,873,394,859,302,879,777,234,494,937,999,867,667,55,273,632,210,153,250,661,802,607,58,349,753,845,839,323,690,96,981,983,453,950,458,117,699,48,848,896,288,806,77,609,729,772,52,490,714,4,367,35,632,668,792,679,194,483,254,988,119,428,426,406,847,539,62,507,753,994,645,659,149,708,847,407,526,505,833,33,76,511,367,77,539,548,696,168,608,982,439,560,176,813,54,947,257,559,788,414,306,534,746,963,501,610,353,285,1,530,244,285,507,115,459,914,734,847,85,849,346,151,646,642,387,525,764,255,102,296,625,969,294,58,253,307,967,487,749,318,890,188,390,54,51,746,952,879,43,693,272,890,990,178,295,366,427,755,17,303,743,42,104,778,456,851,636,714,551,415,612,421,978,613,161,679,608,42,112,583,636,267,885,585,61,972,331,172,351,203,605,433,708,756,218,595,632,675,576,100,612,305,202,512,683,817,288,659,849,405,406,943,395,227,294,748,189,191,596,400,520,686,996,85,514,683,702,654,449,131,961,489,198,770,725,198,155,624,244,282,513,540,40,975,476,644,382,450,318,19,920,70,776,964,554,286,955,783,185,878,375,27,53,380,999,874,550,810,611,311,710,143,69,575,854,232,719,753,626,85,496,368,411,316,742,321,278,212,390,876,185,705,146,921,272,792,843,913,301,696,194,121,156,907,620,796,210,108,807,894,754,254,452,5,592,422,630,939,223,891,240,720,178,528,493,146,614,116,418,268,83,924,438,67,155,164,848,912,902,519,205,300,664,822,405,896,39,147,542,418,56,872,977,969,789,110,891,40,388,277,664,392,256,207,861,444,870,207,639,894,448,963,862,466,82,499,973,853,6,623,841,48,789,277,326,748,69,787,67,788,701,290,739,465,771,512,89,57,760,534,943,811,422,247,668,472,114,725,735,795,288,342,314,851,353,343,608,245,69,3,764,251,970,130,532,402,515,68,438,195,827,747,175,7,983,137,565,810,546,525,796,270,984,9,642,4,68,412,658,162,200,785,442,932,394,28,937,540,749,538,690,832,648,391,756,664,333,284,181,981,797,449,357,303,876,655,559,641,560,189,794,894,729,94,734,426,506,429,1,646,522,49,693,985,535,70,519,15,315,454,573,793,652,989,790,602,964,138,378,411,616,907,213,829,600,859,587,75,829,672,85,49,625,197,694,311,219,173,200,131,821,607,96,637,107,491,561,660,562,328,673,710,655,800,184,622,15,623,257,323,879,203,723,517,887,376,438,99,702,835,430,937,895,88,700,334,793,766,510,555,767,244,19,32,91,682,593,561,920,94,847,88,445,987,116,650,522,512,652,898,289,177,678,186,803,609,958,528,283,43,526,942,736,71,573,505,610,362,68,561,50,612,722,126,685,844,470,835,685,666,440,569,564,490,728,274,908,236,554,618,254,242,136,634,316,935,64,157,358,233,403,441,192,779,301,310,592,895,833,155,842,191,954,977,147,322,632,331,467,208,536,42,501,600,967,124,225,753,340,320,712,532,693,743,236,351,524,394,322,693,629,787,100,364,247,467,990,272,282,687,955,234,688,777,545,610,540,807,154,495,285,283,925,908,41,18,865,621,811,768,555,315,481,541,927,632,54,634,294,530,932,742,260,66,374,1000,270,819,749,866,681,346,790,913,199,494,126,186,122,393,429,936,182,96,283,391,319,226,471,927,796,899,9,148,696,367,335,576,417,519,854,738,637,276,225,124,386,361,424,953,169,68,204,596,889,796,239,43,429,280,923,261,332,612,449,559,415,893,773,633,717,574,322,28,866,985,532,468,734,61,879,660,683,293,140,148,824,814,929,153,415,760,926,241,955,805,462,207,893,458,104,617,643,426,258,241,779,660,390,549,141,199,952,60,714,782,77,822,828,742,244,7,802,267,794,570,500,180,47,649,384,555,327,810,237,252,396,493,858,112,270,699,338,373,755,292,733,917,114,61,528,83,810,466,949,881,580,65,18,602,776,897,836,372,703,504,821,32,573,179,826,577,434,212,693,814,912,686,996,362,620,675,242,119,674,611,226,150,593,165,193,994,912,558,85,292,492,826,386,46,995,432,950,127,770,369,94,603,470,476,297,506,584,748,222,826,261,723,574,779,200,687,386,741,711,397,605,976,739,376,456,788,875,5,746,313,701,510,907,655,221,429,416,101,221,980,212,430,665,308,781,213,555,649,121,24,17,637,234,22,392,282,134,340,990,613,637,474,272,502,600,839,108,982,455,551,786,813,304,380,153,272,897,105,445,980,27,31,822,785,226,244,26,992,522,40,871,429,565,425,743,523,756,805,859,792,944,925,962,543,337,595,240,697,337,323,24,897,520,305,123,278,109,91,63,785,880,592,670,166,373,130,320,545,626,680,475,672,609,139,378,659,842,95,40,818,681,788,816,437,651,132,133,248,41,735,648,269,461,20,226,108,157,669,58];