박종훈 알고리즘 블로그

(Leetcode) 121 - Best Time to Buy and Sell Stock

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

array 문제다. 동시에 DP 문제다.

심플하게 생각하기

그냥 모든 상황에 대해서 가격을 계산한 후 max 값을 반환한다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max = 0

        current = 0
        while current < len(prices):
            currentPrice = prices[current]
            for price in prices[current + 1:]:
                if price - currentPrice > max:
                    max = price - currentPrice
            current += 1

        return max

아래와 같은 입력값에 대해서 시간 복잡도 초과가 발생되었다.

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

고도화 해보기

pointer를 2개 써야한다.

한 날(buy)을 기준으로 특정한 날(sell)에 판매했을 때의 최대 이익을 계산한다.

여기서 생각해볼 점은 다음날 값이 내려간다면, 그 날은 최대 이익이 발생할 수 있는 날은 아니라는 것이다.

다음날 값이 내려간다면 그 날은 최대 이익이 발생하는 날이 아님.

내려간 만큼 다음날에는 더 큰 이득을 얻을 수 있을 것이기 때문이다.

따라서 값이 내려갈 경우에는 거기서부터 다시 계산을 시작한다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 1:
            return 0

        maxProfit = 0

        buy = 0
        sell = 1

        while buy < len(prices) and sell < len(prices):
            if prices[sell] < prices[buy]:
                buy = sell
                sell = buy + 1
            else:
                maxProfit = max(maxProfit, prices[sell] - prices[buy])
                sell += 1

        return maxProfit

최종적으로 위와 같이 작성되었다. easy 문제로 되어있는데 개인적으로는 지금까지 문제중에서 가장 어려웠던것 같다.

(24.04.24 추가) java 풀이 추가

class Solution {
    public int maxProfit(int[] prices) {
        int buyAt = 0;
        int profit = 0;

        for(int i = 1; i < prices.length; i++) {
            if (prices[i] < prices[buyAt]) {
                buyAt = i;
            } else {
                profit = Math.max(profit, prices[i] - prices[buyAt]);
            }
        }

        return profit;
    }
}

TC, SC

이 풀이의 시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , array , two pointer , profit