Android Question I Need Sub Code that Can Compute Large and Very Large Exponential

[omo]

I need b4x code that can compute large and very large exponential like 3^935687429879864897 or more. Answer to this sample should be: 2.19222399769E+446436360569697305

I have tried different methods and algorithms to no effect. I also tried some AI, but couldn't get right code with stable solution.

I tried also to use Bigdecimal library in the forum, once the exponent digits is more than 5 or 6, the app hangs and force to restart. Try and catch couldn't solve it either.

If your solution can solve this even if it is using java object in b4x or bigdecimals in b4x ( in case I didn't use it well) or other algorithms, I don't mind. So far your solution can solve this and more:

3^935687429879864897 and get this result: 2.19222399769E+446436360569697305 or close to it.
Then, your solution should be ok and robust enough to handle more or less

Thank you in advance

 

[omo]

Lastly, to report back on my suspense; there is no issue of @rwblinn solution not performing further computation with other existing bignumber library implementation in the forum that I used. For example, when I reduced the number of digits I e 3^935687425 (maximum of 9 exponent), further computation can be done without problem i.e 3^935687425x7 ; can work well, but once it is above 9 digits I e 3^9356874251x7 ; it will not work further, the problem should be with my existing system which I will try to locate the issue and correct. Thanks, all

 

[emexes]

Is this another algorithm you could have used or just a clearification of term usage?

It was a quick way of checking that a number is divisible by 3.

The result of your example of 3^935687429879864897 should be divisible by 3.

What you do is sum all the digits, and repeat until you are down to a single digit. If that digit is a multiple of 3 ie 3, 6 or 9, then the original number is also a multiple of 3 ie divisible by 3.

Example: is 365 divisible by 3? 3 + 6 + 5 = 14, and then 1 + 4 = 5, which is not a multiple of 3 (ie not 3, 6 or 9) therefore 365 is not a multiple of 3

Example: is 768 divisible by 3? 7 + 6 + 8 = 21, and then 2 + 1 = 3, which is obviously a multiple of 3, therefore 768 is a multiple of 3

There is a similar algorithm for confirming that a multiplication is correct (or at least, not incorrect). Come to think of it, probably for confirming addition too, although not quite as useful since it takes as long to work out as it does to do the actual addition.

 

[emexes]

The result of your example of 3^935687429879864897 should be divisible by 3.

But the check is a bit of a moot exercise here anyway since your result has 446436360569697306 digits and even if you summed a billion digits per second it's still going to take more than 14 years.

On the bright side, only the first pass takes a long time.

The second pass will be summing the digits of approximately 446436360569697306 * 4.5 = 2,008,963,622,563,637,877 which is only 19 digits to be summed.

The 4.5 is the average value of a digit 0..9 (assuming they're evenly distributed) (but even if they're not, the worst case is 9, which is still only 19 digits to be summed).

 

[emexes]

unlike bignumber library in the forum that hangs once the digits is more than 6digits and forces app to restart

Yikes.

Perhaps there is a parameter that determines the maximum length of a number and it has a default of a million.

Or perhaps that limit is hardcoded.

 

[omo]

... it takes as long to work out as it does to do the actual addition.

You have identified the future challenge I may encounter. I am not sure it will be accurate compare to approved solution up here if actually I get the code to implement it. Why? Because, in one of my attempts; AI suggested using modulus approach which I already found in the forum using bignumber/bigdecimal library in the forum.

AI suggested I have to assume value for "mod" part,n even though I don't need it to find some multiple of number odd and even. When I ran the code, I wasn't quite satisfy with the result. So , I abandoned it! I may face similar fate if this your approach is implemented at least for learning purpose or if its accuracy can challenge the approved one on the hot seat with crown now

 

[omo]

Yikes.

Perhaps there is a parameter that determines the maximum length of a number and it has a default of a million.

Or perhaps that limit is hardcoded.

I thought so, but couldn't trace such especially since other bigdecimal subs I already implemented didn't give that kind of limitation and when I first changed to another method, no such restriction. The only restriction I thought may cause it (though not sure since I haven't tried it) is the int limit in pow(n as int); so that integer maybe the limitation when trying to pass bigdecimal, biginteger to it.

I tried to write another user defined method for pow() that will accept biginteger or bigdecimal that can call, I have written it, but not yet run untill "rwblinn" solution came. If it works, then; that int argument may be the limitation causing it to hang. I will still find time to run it for learning purpose

 

[emexes]

If you could limit the result requirement to say 100 million digits, eg 3 ^ 209590327 then we could do it "manually".

Maybe even 200 or 300 or 400 million digits. Limiting factor is available memory for a Java program, to store 2 or 3 such numbers.

 

[emexes]

Thinking about it, we could probably calculate the lower 18 digits pretty quick, using 64-bit integers.

That massive exponent 446436360569697305 only needs Log2(446436360569697305) * 1.5 multiplications, ie about 90 multiplications.

In order to use 64-bit integers, we'd need to do them Mod 1,000,000,000,000,000,000 to "mask" the result decimally to 18 digits, which usefully also keeps the intermediate values within 64-bit integer range ie < 2^63 = max 9,223,372,036,854,775,807.

But to multiply two 100 million digit numbers is going to take that about many digit multiplications and additions squared ie 10,000 million million multiplications and additions, which is going to take a while just to do once, let alone 90 times.

Like, rough estimate, if we do a billion a second, then we're talking 20 million seconds = 231 days. And we have to do about 90 of them, so that's 57 years.

Admittedly we could speed it up by operating on groups of decimal digits, and caching the per-digit multiplications, but still... 100 million digits is still looking to be too slow. 1 million digits feels doable, 10 million digits would be a hundred times slower but perhaps still doable.

18 digits would be blazingly fast.

 

[omo]

If you could limit the result requirement to say 100 million digits, eg 3 ^ 209590327 then we could do it "manually".

Maybe even 200 or 300 or 400 million digits. Limiting factor is available memory for a Java program, to store 2 or 3 such numbers.

If I would have prefer limiting it to 400million digits, but there will still be problem because I can't control what number users will enter. Although, I can programmatically limit the entry if exponent is more than certain digits i.e 9 or 10 digits, then I put a warning overflow message. But in this context, I don't want to limit entry for users, but I am not rigid about it. I can still be forced to do so if there is no solution at hand.

However, these questions that pop of my head are that where if I accept limiting to 400million:
1. Implementing it programmatically will be a problem for me since you mentioned "manually"
2. What of if for example, users enter numbers that we can quickly determine their multiples and another users enter numbers that their multiples can not quickly be determined as applied to this context if implemented.
3. I am still not very clear when we talk about bit limitation in java/b4x data type including bignumber I earlier used to solve it(although I can't really say is the problem because it works in many other areas I used it), but how did the solution approved (big decimal java) able to represent deficient missing bits?
NB: I understood that since your own solution you are proposing now is not trying to use bigdecimal, that is why the bit deficiency persists, right?

I would have loved to see the solution from you that have more experience than me in this field especially if it can represent 400 million (limitation) as stated above

4. I guess that limitation; both exponent and base changes will amount to that 100 million or 400 million, right? Why I asked this is if you have 3^567884 , if I limit user to 6 exponent digits because it meets 100 million maximum; a situation where the base increase I've 8955734^56; it means my restriction via exponent will not work because raise to power four digits may be enough to fill 100 million or is that not how it works?

 

[Daestrum]

Shame you can't call python - it does it in 7 lines (200 digit limit on answer)

Estimated: 2.1922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095541992120884468498898937741186884091581092 × 10^446436360569697305.0

 

[omo]

Shame you can't call python - it does it in 7 lines (200 digit limit on answer)

Estimated: 2.1922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095541992120884468498898937741186884091581092 × 10^446436360569697305.0

Thank you, it would have been another good solution, but unfortunately; I can't call python in b4a. No #If python...#end if yet in b4a. However, you can put the code here or put it as snippet in b4j for those in future that may need similar solution in b4j and find this thread; the thread is already becoming a tutorial center on its own. I don't even need up to 200 digits, only 12 or 14 mantissa précision scale is Ok for my usage, though, I can also set that in bigdecimal b4a and java

 

[Daestrum]

See post #30 - B4J only (not for B4A)

from mpmath import mp

mp.dps = 100 # Set precision
base = mp.mpf('3')
exponent = mp.mpf('935687429879864897')
log10_result = exponent * mp.log10(base)

mantissa = mp.power(10, log10_result - mp.floor(log10_result))
print(f"Estimated: {mantissa} × 10^{mp.floor(log10_result)}")

 

[omo]

...Like, rough estimate, if we do a billion a second, then we're talking 20 million seconds = 231 days. And we have to do about 90 of them, so that's 57 years...

Are you talking "manually/theoretically" or programmatically? It implies user will experience computation delay, right? Users can wait for more than 1 minute to get computation done. If such delay will be noticeable, then there is no need to attempt coding it.

Admittedly we could speed it up by operating on groups of decimal digits, and caching the per-digit multiplications, but still...

Or maybe if I run a sample and experience such delay. But if really the delay is practically glaring to users, then no need to waste effort implementing it.

 

[omo]

from mpmath import mp

mp.dps = 100 # Set precision
base = mp.mpf('3')
exponent = mp.mpf('935687429879864897')
log10_result = exponent * mp.log10(base)

mantissa = mp.power(10, log10_result - mp.floor(log10_result))
print(f"Estimated: {mantissa} × 10^{mp.floor(log10_result)}")

Very Good, précise; but try to put B4J solution only or if they see my comment here in the future, they will know is for B4J only to solve large and very large exponent. Thank you

 

[emexes]

If your solution can solve this

Righto, after a lazy Sunday evening with the tv in the background, I have handcoded some big natural numbers routines (turns out you only need two routines - multiplication, and shift right one bit) and so if you use these Subs:

Sub MaxInt(N1 As Int, N2 As Int) As Int
    If N1 > N2 Then
        Return N1
    Else
        Return N2
    End If
End Sub

Sub GetDigitAt(S As String, I As Int) As Int
    Dim LastChar As Int = S.Length - 1
    If I > LastChar Then Return 0
    Return Asc(S.CharAt(I)) - 48
End Sub

Sub GetDigitAtReverse(S As String, I As Int) As Int
    Dim LastChar As Int = S.Length - 1
    If I > LastChar Then Return 0
    Return Asc(S.CharAt(LastChar - I)) - 48
End Sub

Sub AddStrings(N1 As String, N2 As String) As String
    Dim Result As String
    Dim Carry As Int

    For I = 0 To MaxInt(N1.Length, N2.Length) - 1
        Dim Sum As Int = GetDigitAtReverse(N1, I) + GetDigitAtReverse(N2, I) + Carry

        Carry = 0
        Do While Sum > 9
            Sum = Sum - 10
            Carry = Carry + 1
        Loop

        Result = Sum & Result
    Next
    
    If Carry <> 0 Then
        Result = Carry & Result
    End If
    
    Return Result
End Sub

Sub RemoveLeadingZeroes(N As String) As String
    Do While N.Length > 1
        If N.CharAt(0) <> "0" Then Exit
        N = N.SubString(1)
    Loop
    Return N
End Sub

Sub ShiftRightString(N As String) As String
    Dim Result As String
    Dim Carry As Int
    For I = 0 To N.Length - 1
        Dim Temp As Int = Carry * 10 + GetDigitAt(N, I)
        Carry = Bit.And(Temp, 1)
        Result = Result & Bit.ShiftRight(Temp, 1)
    Next
    
    Return RemoveLeadingZeroes(Result)
End Sub

Sub MultiplyStrings(N1 As String, N2 As String) As String
    Dim ResultSize As Int = N1.Length + N2.Length
    Dim P(ResultSize) As Int
    
    For I1 = 0 To N1.Length - 1
        Dim D1 As Int = GetDigitAtReverse(N1, I1)
        For I2 = 0 To N2.Length - 1
            Dim D2 As Int = GetDigitAtReverse(N2, I2)
            P(I1 + I2) = P(I1 + I2) + D1 * D2
        Next
        
        For I = 0 To ResultSize - 2
            Do While P(I) > 9
                P(I) = P(I) - 10
                P(I + 1) = P(I + 1) + 1
            Loop
        Next
    Next
    
    Dim Result As String
    For I = 0 To ResultSize - 1
        Result = P(I) & Result
    Next
    
    Return RemoveLeadingZeroes(Result)
End Sub

Sub Commas(N As String) As String
    For I = N.Length - 3 To 1 Step -3
        N = N.SubString2(0, I) & "," & N.SubString(I)
    Next
    Return N
End Sub

Sub RandomNumber(L As Int) As String
    Dim Result As String = Rnd(1, 10)
    For I = 2 To L
        Result = Result & Rnd(0, 10)
    Next   
    Return Result
End Sub

Sub LimitString(N As String, L As Int) As String
    If L > 0 Then
        If N.Length > L Then
            N = N.SubString2(0, L + 1)
            N = AddStrings(N, "5")
            N = N.SubString2(0, L)
        End If
    End If
    Return N
End Sub

Sub PowerStrings(Base As String, Exponent As String, LimitLength As Int) As String
    Dim Result As String = "1"
    Dim Term As String = Base
    
    Do While Exponent <> "0"
        If Bit.And(GetDigitAtReverse(Exponent, 0), 1) <> 0 Then
            Result = MultiplyStrings(Result, Term)
            Result = LimitString(Result, LimitLength)
        End If
        
        Exponent = ShiftRightString(Exponent)
        If Exponent = "0" Then Exit

        Term = MultiplyStrings(Term, Term)
        Term = LimitString(Term, LimitLength)
    Loop
    Return Result
End Sub

and test them with this:

Log("Power" & TAB & "Digits" & TAB & "Value")
For I = 0 To 1000 Step 7
    Dim Temp As String = PowerStrings("3", I, 0)
    Log(I & TAB & Temp.Length & TAB & Commas(Temp))
Next

Dim B As String = "3"
Dim E As String = "935687429879864897"
Log("MaxDig" & TAB & "Value")
For LimitLength = 1 To 1000 Step 7
    Log(LimitLength & TAB & PowerStrings(B, E, LimitLength))
Next

then you get promising-looking results like:

Waiting for debugger to connect...
Program started.
Power    Digits    Value
0    1    1
7    4    2,187
14    7    4,782,969
21    11    10,460,353,203
28    14    22,876,792,454,961
35    17    50,031,545,098,999,707
42    21    109,418,989,131,512,359,209
49    24    239,299,329,230,617,529,590,083
56    27    523,347,633,027,360,537,213,511,521
63    31    1,144,561,273,430,837,494,885,949,696,427
70    34    2,503,155,504,993,241,601,315,571,986,085,849
77    37    5,474,401,089,420,219,382,077,155,933,569,751,763
84    41    11,972,515,182,562,019,788,602,740,026,717,047,105,681
91    44    26,183,890,704,263,137,277,674,192,438,430,182,020,124,347
98    47    57,264,168,970,223,481,226,273,458,862,846,808,078,011,946,889
105    51    125,236,737,537,878,753,441,860,054,533,045,969,266,612,127,846,243
112    54    273,892,744,995,340,833,777,347,939,263,771,534,786,080,723,599,733,441
119    57    599,003,433,304,810,403,471,059,943,169,868,346,577,158,542,512,617,035,467
126    61    1,310,020,508,637,620,352,391,208,095,712,502,073,964,245,732,475,093,456,566,329
133    64    2,865,014,852,390,475,710,679,572,105,323,242,035,759,805,416,923,029,389,510,561,523
140    67    6,265,787,482,177,970,379,256,224,194,341,930,332,206,694,446,810,665,274,859,598,050,801
147    71    13,703,277,223,523,221,219,433,362,313,025,801,636,536,040,755,174,924,956,117,940,937,101,787
154    74    29,969,067,287,845,284,806,900,763,378,587,428,179,104,321,131,567,560,879,029,936,829,441,608,169
161    77    65,542,350,158,517,637,872,691,969,508,970,705,427,701,150,314,738,255,642,438,471,845,988,797,065,603
168    81    143,341,119,796,678,074,027,577,337,316,118,932,770,382,415,738,332,565,090,012,937,927,177,499,182,473,761
175    84    313,487,028,995,334,947,898,311,636,710,352,105,968,826,343,219,733,319,851,858,295,246,737,190,712,070,115,307
182    87    685,596,132,412,797,531,053,607,549,485,540,055,753,823,212,621,556,770,516,014,091,704,614,236,087,297,342,176,409
189    91    1,499,398,741,586,788,200,414,239,710,724,876,101,933,611,366,003,344,657,118,522,818,557,991,334,322,919,287,339,806,483
196    94    3,279,185,047,850,305,794,305,942,247,355,304,034,928,808,057,449,314,765,118,209,404,186,327,048,164,224,481,412,156,778,321
203    97    7,171,577,699,648,618,772,147,095,694,966,049,924,389,303,221,641,651,391,313,523,966,955,497,254,335,158,940,848,386,874,188,027
210    101    15,684,240,429,131,529,254,685,698,284,890,751,184,639,406,145,730,291,592,802,676,915,731,672,495,230,992,603,635,422,093,849,215,049
217    104    34,301,433,818,510,654,479,997,622,149,056,072,840,806,381,240,712,147,713,459,454,414,705,167,747,070,180,824,150,668,119,248,233,312,163
224    107    75,017,235,761,082,801,347,754,799,639,985,631,302,843,555,773,437,467,049,335,826,804,960,201,862,842,485,462,417,511,176,795,886,253,700,481
231    111    164,062,694,609,488,086,547,539,746,812,648,575,659,318,856,476,507,740,436,897,453,222,447,961,474,036,515,706,307,096,943,652,603,236,842,951,947
238    114    358,805,113,110,950,445,279,469,426,279,262,434,966,930,339,114,122,428,335,494,730,197,493,691,743,717,859,849,693,621,015,768,243,278,975,535,908,089
245    117    784,706,782,373,648,623,826,199,635,272,746,945,272,676,651,642,585,750,769,726,974,941,918,703,843,510,959,491,279,949,161,485,148,051,119,497,030,990,643
252    121    1,716,153,733,051,169,540,307,898,602,341,497,569,311,343,837,142,335,036,933,392,894,197,976,205,305,758,468,407,429,248,816,168,018,787,798,340,006,776,536,241
259    124    3,753,228,214,182,907,784,653,374,243,320,855,184,083,908,971,830,286,725,773,330,259,610,973,961,003,693,770,407,047,767,160,959,457,088,914,969,594,820,284,759,067
266    127    8,208,310,104,418,019,325,036,929,470,142,710,287,591,508,921,392,837,069,266,273,277,769,200,052,715,078,275,880,213,466,781,018,332,653,457,038,503,871,962,768,079,529
273    131    17,951,574,198,362,208,263,855,764,751,202,107,398,962,630,011,086,134,670,485,339,658,481,240,515,287,876,189,350,026,851,850,087,093,513,110,543,207,967,982,573,789,929,923
280    134    39,260,092,771,818,149,473,052,557,510,879,008,881,531,271,834,245,376,524,351,437,833,098,473,006,934,585,226,108,508,724,996,140,473,513,172,757,995,825,977,888,878,576,741,601
287    137    85,861,822,891,966,292,897,565,943,276,292,392,423,908,891,501,494,638,458,756,594,540,986,360,466,165,937,889,499,308,581,566,559,215,573,308,821,736,871,413,642,977,447,333,881,387
294    141    187,779,806,664,730,282,566,976,717,945,251,462,231,088,745,713,768,774,309,300,672,261,137,170,339,504,906,164,334,987,867,886,065,004,458,826,393,138,537,781,637,191,677,319,198,593,369
301    144    410,674,437,175,765,127,973,978,082,146,264,947,899,391,086,876,012,309,414,440,570,235,106,991,532,497,229,781,400,618,467,066,824,164,751,453,321,793,982,128,440,538,198,297,087,323,698,003
308    147    898,144,994,103,398,334,879,090,065,653,881,441,055,968,306,997,838,920,689,381,527,104,178,990,481,571,441,531,923,152,587,475,144,448,311,428,414,763,438,914,899,457,039,675,729,976,927,532,561
315    151    1,964,243,102,104,132,158,380,569,973,585,038,711,589,402,687,404,273,719,547,677,399,776,839,452,183,196,742,630,315,934,708,808,140,908,457,093,943,087,640,906,885,112,545,770,821,459,540,513,710,907

(edited out due post limited to 50000 characters)

994    475    1,813,540,218,766,538,596,557,551,796,642,173,341,516,353,954,392,521,491,995,775,539,405,800,545,057,208,366,996,952,419,548,159,207,083,552,507,128,768,974,425,172,777,204,527,597,958,663,021,570,998,564,710,600,302,092,178,766,534,812,091,597,021,899,645,095,185,734,043,331,437,642,152,191,790,978,181,670,866,345,916,397,924,107,668,732,754,630,288,538,279,214,066,388,256,372,863,464,153,984,795,797,285,089,531,637,556,354,307,583,561,588,899,709,049,270,996,439,073,935,442,536,863,157,986,071,824,332,915,660,857,364,801,904,127,654,905,472,800,327,659,948,990,878,443,962,616,139,687,257,358,526,930,278,604,621,265,919,369

and these ever-increasing leading-digits of your 3 ^ 935687429879864897 example, made possible by restricting the number of digits during the exponentiation:

MaxDig    Value
1    4
8    89854634
15    145095251568264
22    2192220973470281257701
29    21922239976913559553660533830
36    219222399769075149647810652444305756
43    2192223997690751496421516744667813063792112
50    21922239976907514964215167476826146794604011622825
57    219222399769075149642151674768261453428550141140588964598
64    2192223997690751496421516747682614534285478814665391051561856525
71    21922239976907514964215167476826145342854788146672476332278719488341409
78    219222399769075149642151674768261453428547881466724763336899837147308820080355
85    2192223997690751496421516747682614534285478814667247633368998403833553854748891849703
92    21922239976907514964215167476826145342854788146672476333689984038335531154430024824599277617
99    219222399769075149642151674768261453428547881466724763336899840383355311544318925345819909574207081
106    2192223997690751496421516747682614534285478814667247633368998403833553115443189253427213388381571752559704
113    21922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086001044968433610856
120    219222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148843678701732896047
127    2192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715809214718543630
134    21922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103619302208900909
141    219222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624451732600457341
148    2192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382854987559977093
155    21922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050326209062266452392
162    219222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980679898565565204097
169    2192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664169277492429311668
176    21922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095542380974571369567
183    219222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208771141945454559
190    2192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664168809554199212088446849312614496548191
197    21922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095541992120884468498898938067490297959569
204    219222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208844684988989377515578657713870414179
211    2192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664168809554199212088446849889893775155780251513436650568503059

(edited out due post limited to 50,000 characters)

981    219222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208844684988989377515578025151264395627155081939581263090608074548466042723182490934689145312953930871182851064183986079134067925984677310439022177320101345524149025558825903433967854686943474825803688963348260933158834752490955461419669244685206532205298147742572460816203466318624029282507658210834394724090083162562234662559008625680585656292511266817511955128367905451337245207517228973169549120777632799358498295710118769733889262732369405738496693993983964749833294517198637320800823190837750230130043108605361474334945685769350410955544020368045259052056534092233610232880505100214730880740598566254184037547064819130453929377162586745862196437188303462640826549240446366113097790962417212298302812711433853070344793699736181077317556090768995967553409433862898710071326226901530059518033590498586345337896807

I've been comparing results with:

Big Number Calculator

This free big number calculator can perform calculations involving very large integers or decimals at a high level of precision.

www.calculator.net

and... so far, so good. Next step is to make the multiplication (and thus exponentiation) handle scientific-format numbers, ie with an exponent value in place of the dropped trailing digits. But not tonight, and probably not during the week.

Oh, and the limiting factor at the moment is speed. Like, on my basic laptop, in Release mode, 3 ^ 100000 is 47713 digits and took just under 15 seconds to calculate. 3 ^ 200000 is twice as many digits and took four times as long (just under a minute). So 3 ^ 1000000 will probably take 25 minutes to produce just under a half-million-digit result, and 3 ^ 2095865 take a couple of hours to produce a million-digit result (cf about 0.3 seconds to produce a thousand-significant-digit result).

 

[omo]

@emexes; this is a very serious and massive hardwork played on at background by your humble self. First, I commend you for this; welldone, the accuracy of the mantissa at display has proven its consistency and stability. The mantissa result is accurate so far, but i will still wait for the exponent anytime it seems convenient to you to balance the method.

Even though the approach is stable and consistent, the only major minor issue here is that it has lengthier code compared to others, but tht lenghty proved to be more beneficial after all because I am even learning from those sub codes and I have found some useful snippets and logic from those subs.

Even that your comma formatting trick will be a choice replacement for me because the numberformat I am using seems to have some challenges with bigdecimal-large number results, but with this your commas formatting; I will use it instead. Each of the subs is useful and your bigdecimal calculator reference is another plus tools that will complément confirming accuracy.

Thank you once again and well done. I look forward to getting exponent part of this solution when convenient for you

Please, don't forget the exponent part when you are free for this method to remain complete for me and future users that may find this thread useful in future.

 

[omo]

"..…So 3 ^ 1000000 will probably take 25 minutes to produce just under a half-million-digit result..."

As you said, it means to process that my example entry: 3^935687429879864897 or 236475^627423852959 ;
Users that enter such massive data in the morning should go back to sleep and come back for answer in the evening, right? Anyway, is good to have it as alternative; it will be useful somewhere, someday aside my initial submission usage cases

 

[emexes]

Please, don't forget the exponent part

Lol read 'em and weep:

MaxDig   Value
3        2.19E+446436360569697305
76       2.192223997690751496421516747682614534285478814667247633368998403833553115443E+446436360569697305
149      2.1922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067867E+446436360569697305
222      2.19222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208844684988989377515578025151264395627155081939581263091E+446436360569697305
295      2.192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664168809554199212088446849889893775155780251512643956271550819395812630906080745484660427231824909346891453129539308711828510641839860791340679260E+446436360569697305
368      2.1922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095541992120884468498898937751557802515126439562715508193958126309060807454846604272318249093468914531295393087118285106418398607913406792598467731043902217732010134552414902555882590343396785468694347482580368896E+446436360569697305
441      2.19222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208844684988989377515578025151264395627155081939581263090608074548466042723182490934689145312953930871182851064183986079134067925984677310439022177320101345524149025558825903433967854686943474825803688963348260933158834752490955461419669244685206532205298147742572460816203466E+446436360569697305
514      2.192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664168809554199212088446849889893775155780251512643956271550819395812630906080745484660427231824909346891453129539308711828510641839860791340679259846773104390221773201013455241490255588259034339678546869434748258036889633482609331588347524909554614196692446852065322052981477425724608162034663186240292825076582108343947240900831625622346625590086256805856562925113E+446436360569697305
587      2.1922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095541992120884468498898937751557802515126439562715508193958126309060807454846604272318249093468914531295393087118285106418398607913406792598467731043902217732010134552414902555882590343396785468694347482580368896334826093315883475249095546141966924468520653220529814774257246081620346631862402928250765821083439472409008316256223466255900862568058565629251126681751195512836790545133724520751722897316954912077763279935849829571012E+446436360569697305
660      2.19222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208844684988989377515578025151264395627155081939581263090608074548466042723182490934689145312953930871182851064183986079134067925984677310439022177320101345524149025558825903433967854686943474825803688963348260933158834752490955461419669244685206532205298147742572460816203466318624029282507658210834394724090083162562234662559008625680585656292511266817511955128367905451337245207517228973169549120777632799358498295710118769733889262732369405738496693993983964749833294517198637320800823190838E+446436360569697305
733      2.192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664168809554199212088446849889893775155780251512643956271550819395812630906080745484660427231824909346891453129539308711828510641839860791340679259846773104390221773201013455241490255588259034339678546869434748258036889633482609331588347524909554614196692446852065322052981477425724608162034663186240292825076582108343947240900831625622346625590086256805856562925112668175119551283679054513372452075172289731695491207776327993584982957101187697338892627323694057384966939939839647498332945171986373208008231908377502301300431086053614743349456857693504109555440203680452590520565340922E+446436360569697305
806      2.1922239976907514964215167476826145342854788146672476333689984038335531154431892534272133864086000014884159877152482103661762475143826050325498067866641688095541992120884468498898937751557802515126439562715508193958126309060807454846604272318249093468914531295393087118285106418398607913406792598467731043902217732010134552414902555882590343396785468694347482580368896334826093315883475249095546141966924468520653220529814774257246081620346631862402928250765821083439472409008316256223466255900862568058565629251126681751195512836790545133724520751722897316954912077763279935849829571011876973388926273236940573849669399398396474983329451719863732080082319083775023013004310860536147433494568576935041095554402036804525905205653409223361023288050510021473088074059856625418403754706481913045392937716258675E+446436360569697305
879      2.19222399769075149642151674768261453428547881466724763336899840383355311544318925342721338640860000148841598771524821036617624751438260503254980678666416880955419921208844684988989377515578025151264395627155081939581263090608074548466042723182490934689145312953930871182851064183986079134067925984677310439022177320101345524149025558825903433967854686943474825803688963348260933158834752490955461419669244685206532205298147742572460816203466318624029282507658210834394724090083162562234662559008625680585656292511266817511955128367905451337245207517228973169549120777632799358498295710118769733889262732369405738496693993983964749833294517198637320800823190837750230130043108605361474334945685769350410955544020368045259052056534092233610232880505100214730880740598566254184037547064819130453929377162586745862196437188303462640826549240446366113097790962417212298302812711433853E+446436360569697305
952      2.192223997690751496421516747682614534285478814667247633368998403833553115443189253427213386408600001488415987715248210366176247514382605032549806786664168809554199212088446849889893775155780251512643956271550819395812630906080745484660427231824909346891453129539308711828510641839860791340679259846773104390221773201013455241490255588259034339678546869434748258036889633482609331588347524909554614196692446852065322052981477425724608162034663186240292825076582108343947240900831625622346625590086256805856562925112668175119551283679054513372452075172289731695491207776327993584982957101187697338892627323694057384966939939839647498332945171986373208008231908377502301300431086053614743349456857693504109555440203680452590520565340922336102328805051002147308807405985662541840375470648191304539293771625867458621964371883034626408265492404463661130977909624172122983028127114338530703447936997361810773175560907689959675534094338628987100713262269015301E+446436360569697305

 

[emexes]

ditto for:

236475^627423852959

MaxDig   Value
3        1.13E+3371641036578
76       1.129090713485875075048519246204394860731341723381569932651606850587387834066E+3371641036578
149      1.1290907134858750750485192462043948607313417233815699326516068505873878340658755018264440650871756017802171767251816490836849844758510996014592700748E+3371641036578
222      1.12909071348587507504851924620439486073134172338156993265160685058738783406587550182644406508717560178021717672518164908368498447585109960145927007476199451396759854551479698304171429401130469854720457906095865991862201190E+3371641036578
295      1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863806E+3371641036578
368      1.1290907134858750750485192462043948607313417233815699326516068505873878340658755018264440650871756017802171767251816490836849844758510996014592700747619945139675985455147969830417142940113046985472045790609586599186220119011430478915213732033280864206635685187864481453501989721468563721368638055328132165367016940503123900047899558550793465146106235652748952520692311E+3371641036578
441      1.12909071348587507504851924620439486073134172338156993265160685058738783406587550182644406508717560178021717672518164908368498447585109960145927007476199451396759854551479698304171429401130469854720457906095865991862201190114304789152137320332808642066356851878644814535019897214685637213686380553281321653670169405031239000478995585507934651461062356527489525206923106956733495858758308665538113461549347823885844670537791663181439242237040E+3371641036578
514      1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863805532813216536701694050312390004789955855079346514610623565274895252069231069567334958587583086655381134615493478238858446705377916631814392422370398629104769309409774144099665043462983980148170453637114624573181579588909E+3371641036578
587      1.1290907134858750750485192462043948607313417233815699326516068505873878340658755018264440650871756017802171767251816490836849844758510996014592700747619945139675985455147969830417142940113046985472045790609586599186220119011430478915213732033280864206635685187864481453501989721468563721368638055328132165367016940503123900047899558550793465146106235652748952520692310695673349585875830866553811346154934782388584467053779166318143924223703986291047693094097741440996650434629839801481704536371146245731815795889092492253469132638406866691337220976191931349018552688316711533020503260359E+3371641036578
660      1.12909071348587507504851924620439486073134172338156993265160685058738783406587550182644406508717560178021717672518164908368498447585109960145927007476199451396759854551479698304171429401130469854720457906095865991862201190114304789152137320332808642066356851878644814535019897214685637213686380553281321653670169405031239000478995585507934651461062356527489525206923106956733495858758308665538113461549347823885844670537791663181439242237039862910476930940977414409966504346298398014817045363711462457318157958890924922534691326384068666913372209761919313490185526883167115330205032603586727134927294431631690681598995787893256193740952846895134848170313223069E+3371641036578
733      1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863805532813216536701694050312390004789955855079346514610623565274895252069231069567334958587583086655381134615493478238858446705377916631814392422370398629104769309409774144099665043462983980148170453637114624573181579588909249225346913263840686669133722097619193134901855268831671153302050326035867271349272944316316906815989957878932561937409528468951348481703132230693805356417915484254383040892803665685350288021811289046000288375102843389E+3371641036578
806      1.1290907134858750750485192462043948607313417233815699326516068505873878340658755018264440650871756017802171767251816490836849844758510996014592700747619945139675985455147969830417142940113046985472045790609586599186220119011430478915213732033280864206635685187864481453501989721468563721368638055328132165367016940503123900047899558550793465146106235652748952520692310695673349585875830866553811346154934782388584467053779166318143924223703986291047693094097741440996650434629839801481704536371146245731815795889092492253469132638406866691337220976191931349018552688316711533020503260358672713492729443163169068159899578789325619374095284689513484817031322306938053564179154842543830408928036656853502880218112890460002883751028433892566911768864335681485386324229717457407537267093581240360957175415835891E+3371641036578
879      1.12909071348587507504851924620439486073134172338156993265160685058738783406587550182644406508717560178021717672518164908368498447585109960145927007476199451396759854551479698304171429401130469854720457906095865991862201190114304789152137320332808642066356851878644814535019897214685637213686380553281321653670169405031239000478995585507934651461062356527489525206923106956733495858758308665538113461549347823885844670537791663181439242237039862910476930940977414409966504346298398014817045363711462457318157958890924922534691326384068666913372209761919313490185526883167115330205032603586727134927294431631690681598995787893256193740952846895134848170313223069380535641791548425438304089280366568535028802181128904600028837510284338925669117688643356814853863242297174574075372670935812403609571754158358905109278146870438374216685339623699379072980515655959642089506499829098392E+3371641036578
952      1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863805532813216536701694050312390004789955855079346514610623565274895252069231069567334958587583086655381134615493478238858446705377916631814392422370398629104769309409774144099665043462983980148170453637114624573181579588909249225346913263840686669133722097619193134901855268831671153302050326035867271349272944316316906815989957878932561937409528468951348481703132230693805356417915484254383040892803665685350288021811289046000288375102843389256691176886433568148538632422971745740753726709358124036095717541583589051092781468704383742166853396236993790729805156559596420895064998290983924817003718446730517003645143503644561607356144251612202947521837391575360E+3371641036578

 

[emexes]

236475^627423852959

or alternatively, and to fit within 50,000 character posting limit:

MaxDig   Value
4        1.129E+3371641036578
40       1.129090713485875075048519246204394860731E+3371641036578
400      1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863805532813216536701694050312390004789955855079346514610623565274895252069231069567334958587583086655381134615E+3371641036578
4000     1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863805532813216536701694050312390004789955855079346514610623565274895252069231069567334958587583086655381134615493478238858446705377916631814392422370398629104769309409774144099665043462983980148170453637114624573181579588909249225346913263840686669133722097619193134901855268831671153302050326035867271349272944316316906815989957878932561937409528468951348481703132230693805356417915484254383040892803665685350288021811289046000288375102843389256691176886433568148538632422971745740753726709358124036095717541583589051092781468704383742166853396236993790729805156559596420895064998290983924817003718446730517003645143503644561607356144251612202947521837391575359728716694606036429147681938974334039833038710740660929541286502846224503255820038807452550436728448424318527107659037881383161585985072975141577234651936929919450665767667660868235666672602776500926331283676016446750629714398304355653530506506590044580665904501483659460477705672791898290673530527649243856283958833239304542592588853131945708251472365249995432167652414167481611393471011762251488136533787541358224894605906376099646593149872836178487632468794457770618898780201961853043720108438966394937339392987465798759501200010179329579548560940084204506271153512548985838266150654118365424405624897825533096968061650010847099330883308374784556429783658083020446938459540304902027495754558070439019059009931521818907786117044883581140475497465457154651508836285576568440116938086460406493507584530184114617444834039805465919299557291996817559745472327650793705730657149025177332588655011728622739444569488567258811700580139402033549559476198924906969040879389611431083673231834365524105804670017969225887005584702198493634658097263793574206096905291305199821442362101725938613878095509023031587840423220336019861150295237655475953751452159970989147278994558798467712704790108531477375386483760511655185208445088085740186248717235110311085280575801748397950326057317338669158981929988757331765122586247926842004818446102272847732981728844309528275301905026114028523317104759015066135514864077424793596070076699133917435461738955474523516381119855040056512369207133314782385193385565950868243363013615358454699181463798207308385328819879725582093219435721881939100439079292958666699442379520259368057901354053479342052947818577483466186129808763275210689449530270278345410298508860757463548775753607972862489422192104592777743966114471283399031431474906785595778910113717586114872212873577446279640839555809239591578710113337374535412768921221646566100692904630459125200324636843204748123450962701273679312330492160497107502954481542010028566903505688729527343065026029878612765652295301026513679112083609491662542733999681254041522604208229230308025788710357020648977897915248111553630675495398775101114788811903341670128949218698315413114954624338430638547784892664044416872418548670055973535932861266602376870490090470202591427578564620382746329141255768680986061621781903171549629330658127438416056814280102276726426737617192957844799765911411168746454032257640408821684163787948012196730495598625899652077990432006264349621066217900858046540854638050626652570710044377640558994355393682579054362348174385053535285207624007091426068821701203314154810424741188273746788596663212614878022865777452333123180634518921539159346610718649488088449118214607695362111888580932042596461289984869917147666655137358965567377189173391917045268959577414459588206876984115624675402954118455149479545654929494748784021046661644613382707424233703734075002119085492499439374391946275608239958143762471457450191566931509670048344012067099185732171680425830549758840674934784778682514789002549535898774389404412455689332659271720207779054144729627491650472204837E+3371641036578
40000    1.129090713485875075048519246204394860731341723381569932651606850587387834065875501826444065087175601780217176725181649083684984475851099601459270074761994513967598545514796983041714294011304698547204579060958659918622011901143047891521373203328086420663568518786448145350198972146856372136863805532813216536701694050312390004789955855079346514610623565274895252069231069567334958587583086655381134615493478238858446705377916631814392422370398629104769309409774144099665043462983980148170453637114624573181579588909249225346913263840686669133722097619193134901855268831671153302050326035867271349272944316316906815989957878932561937409528468951348481703132230693805356417915484254383040892803665685350288021811289046000288375102843389256691176886433568148538632422971745740753726709358124036095717541583589051092781468704383742166853396236993790729805156559596420895064998290983924817003718446730517003645143503644561607356144251612202947521837391575359728716694606036429147681938974334039833038710740660929541286502846224503255820038807452550436728448424318527107659037881383161585985072975141577234651936929919450665767667660868235666672602776500926331283676016446750629714398304355653530506506590044580665904501483659460477705672791898290673530527649243856283958833239304542592588853131945708251472365249995432167652414167481611393471011762251488136533787541358224894605906376099646593149872836178487632468794457770618898780201961853043720108438966394937339392987465798759501200010179329579548560940084204506271153512548985838266150654118365424405624897825533096968061650010847099330883308374784556429783658083020446938459540304902027495754558070439019059009931521818907786117044883581140475497465457154651508836285576568440116938086460406493507584530184114617444834039805465919299557291996817559745472327650793705730657149025177332588655011728622739444569488567258811700580139402033549559476198924906969040879389611431083673231834365524105804670017969225887005584702198493634658097263793574206096905291305199821442362101725938613878095509023031587840423220336019861150295237655475953751452159970989147278994558798467712704790108531477375386483760511655185208445088085740186248717235110311085280575801748397950326057317338669158981929988757331765122586247926842004818446102272847732981728844309528275301905026114028523317104759015066135514864077424793596070076699133917435461738955474523516381119855040056512369207133314782385193385565950868243363013615358454699181463798207308385328819879725582093219435721881939100439079292958666699442379520259368057901354053479342052947818577483466186129808763275210689449530270278345410298508860757463548775753607972862489422192104592777743966114471283399031431474906785595778910113717586114872212873577446279640839555809239591578710113337374535412768921221646566100692904630459125200324636843204748123450962701273679312330492160497107502954481542010028566903505688729527343065026029878612765652295301026513679112083609491662542733999681254041522604208229230308025788710357020648977897915248111553630675495398775101114788811903341670128949218698315413114954624338430638547784892664044416872418548670055973535932861266602376870490090470202591427578564620382746329141255768680986061621781903171549629330658127438416056814280102276726426737617192957844799765911411168746454032257640408821684163787948012196730495598625899652077990432006264349621066217900858046540854638050626652570710044377640558994355393682579054362348174385053535285207624007091426068821701203314154810424741188273746788596663212614878022865777452333123180634518921539159346610718649488088449118214607695362111888580932042596461289984869917147666655137358965567377189173391917045268959577414459588206876984115624675402954118455149479545654929494748784021046661644613382707424233703734075002119085492499439374391946275608239958143762471457450191566931509670048344012067099185732171680425830549758840674934784778682514789002549535898774389404412455689332659271720207779054144729627491650472204837218156819298571171376817890285662157827691293765859467190476296611188534785554094767412347596890122549654500706524680769508948940511790664787502201866055173982402250248857923201612215739119047972206260158235567238629536142101120032139204018768722370241354105645366522432706691267281859534726857739808995825707785542450318676938882113182360247212421460730032271846188762707055844058072041658610113476552848797919627471435905292220194253531290884222589479662722227702243215789501568642756632529837461451300298216201766539629775341261117767967208932548419955672132464209206225637757833717220339007118858072465404391680902041855832504636230437505270585279465518815034836355354664527719576708460243774168324780629448063324122287576636074599593429369239697137423873780837918789046927590090199980005594078446088365975929050358497935999330450040042267980083330820970541435582554534776055585200581423081858066421757927892293269073269819785065641977515330351134267895385290006576693571432596378024091410881261144104735206533385787066445713399542387391718199133698115704220316405144713522442755893352080998839489413612698371152338649265089971357536923142084133702941718443702644329100400923850608991493903872778591501030325300883926663902753321720709944534201132559384222900298925427329200044133537406967180365054011491821878022536635125098599708662861781308074467244769260219437310804779869794653494681532720775260417906851828018104006978296856730473437089594968646793152013618419658610954218401005088128699475829589312063331785002493253695195876201165736567984310627593432070528126098925830185816128690425320596317989286893869241751505800344958397092686218339981147253508559249464004761737932523173101759543371236902124644591141788947701311609568558238125891369542588518476541182456227630512033639901093788104199599876835045726213308883764442988342754030691890002084443678492387100724710602867431478737950905870181347330245325626343771718226452903291317651266668662896893966539599052192038497514581823332137432526198936772502078779962450208531621891495980381733534817967303227725038211078168845229030260445738992176533504679405659467154554609013153105930817436325557731617414532496936652800902052940471573804517277548205034377374742833083366552429249577354221018543130761394193279661150448091692077828491104446683741934921686618493164159329337944063696042908332260168215230804205258043944988733948348191885160422013519881765915257061412724420213472977289557778080692181881668166941142555736714481948720652496175654345811075491935312433627612672293356569288479151092778149741282180059125908054599483730589266455711240610315436665718145938477566237507071079554409021288036157427425449663511570655427621918831136442990573512634950519227650428789031044833713414997802445790008396380491432021493302412303318123500510897972550846674890645957103634649155750377245233155462954653287695647045099373980674769870918079156319802470789802372987872530489915684813949372263504347284251380609590482354688566755220701202366670824683108836333705844178878568325126089147983036820638808828679155373707869072153049338437491640088669137570206304018512219648322548363409560839185808197843890011042158572152831700630096555395929860199642374534008434797779743566486176591857726519746009137016337540399455896415042770491273914738740442173110299489895508032820289441464495420707429202581750488641972237593539661690339099224427927682408709757165941135323690290738001823110973230017121117504267986584645429681455927071569774360550795285273604513030836561366652098444992861146848283982369621102426045434882486120300506935402770555180275931358694824327186370632553013668019511209665079210087642053512809518680631483159054777993034516112239731849506514693871886007728928230292682049736136452105078160833268021508402944914927627822996530410146185821530907744705161126532467281337707730534562597470669768401345559361933703360811107772520755212949090089126824006886535620279457654674027109817150383598452490363470504566467533068268211186360758187799639042400234630138569483482008957843255736177426472394735087154002545804698263655017588796329193715714906724445358550493817412120827609150948488564585446227363776892354849568909866493349387558325100849774707880475851774677583313937928155922999416777094283970589585300164169801479690254005217247471669649152081493930083012992550684121833124410570051018696457041673483694242867342047261340236116540907682398420053847837197216256617125775307553056203653396979901720696616703258679456788162294206053913548357088058359367171236299979312939373599206076656626152359114456250027136771481508230658771480540513186950080752208559086511865042703248697334638443723852931495946264403071635806854562889456561168801001573303152623049108792795815637339792332902764048754264952382096839177013794074929732890439136237024429764635765952147489390779031439762285822238535715084769001645617649253694019551228698508358412438691937417066637539221202415735390599596876377839107773476811215436277742454591359860881177874882650686528793120550289300313629245773025373449116987253111070179811790308866207371301200450494432252150319450633088647902334691901232336241733636542894876338274449018211974826766769739394300274541792483158255343115330149514748037001924203406769654850116455222739089877220030788204419728438087050322409901384425224576599531871534896337502182579214473658984105395068851305747873326053170309313439016468937263812651636714127115856026786012122698012817548386541497978958700699610660140498653362203893400165181185210988992063821190710505578653026012729570108104504737401875116384645178889644314592994806588185745492908051084531540289823973111115547406181057568473899904485010988813508779688247860324366662699570318875491314602748976535087794823791573988988788166118356832954144229465268001411335063928351028755529847618988617168144163760097925229346905985798444606819314860768260578308940607653380693982532163433216886418063668806555577506477379858061131163518434720012652049116228906485859322740300978531529558909897295339515146876143151532374985937371827667438790324458695145232258716675750534331926953289189588220495047140295242470080282441946837499352423463300286240883636987840728828725034122435163979324870455020618419982259170739814946094592359396449294876858694065599935258892912443339805597849296903976182510657149287627240175260444244279690573829245199790673793491518437387198283703133760935076500117913558312178472554523646675233722998866852899129384468772719118387633036988745680382157888329367352657166350485599720653771110590287121975479137371591258117409008415341117672857270525950175141372866350413915865258947002620000185708428460381765413674697850581337894803244022853017191999881282967422650387637307301578249570425320867031628894629317839416775890586051985266007888313678042942195204152067878392706966955196443036613956629424382520814828134382760871606780275853031377400892028695589146057547499586883250779201472408864606285558456865945456583566726166935777702949181512166288634870512084047830341811946690180686861491522495049288035105406653232842983634103269573927284558683701190652160823251817696409402970115301633145506705738094206667715519345351534083750652346028157354396539011997782091091508375177570077209091007513394764702831585083686799035030216094216501768668879572149585813894601853486577105032902170318519506744755446527070329355843185737876513571893541506092860315512060701448539515324228141161016133324600730570548080324359126530681398268474243338354923952460022059677336423424042296576619582214044394927459754234317469705581842778197445172468758273222952093084978560120928636244792453576615540180134157548317011880373398210561547598179232836922659582270016077792034786862130328362542132666997617826040956854888688725894067138064071771876775963933549984706549903676348868600572586972443306943869913507482274639942839073147980811485198360287843401926600766538235757283848361935001105952955093384083293995165214267831975338732761096191807674809854577977684983009280029627854908660075916379932292300384193636429321593756628954798054423818309424369025289974650302784650259036712797669383448564424916252673735020586086443751231459429365027475334967217347403678591073594446858897925089984462222409979433262045444461872408245331907628346709531256157862892672202132177915916776419167723786154830100995578376589786994389071601030072842555615192890735819001492767394911443718986095076121825741780883610928241952930612596541995893734421079728968288518601919659346787787559876396906597502295490435085932424614138675008122263167633816289529722598339392453273055795582702131507576523034067914810469580876684819295925780357012401807618538240869198096650782728859057705752409618111223785216586065231004625068910325283939694783189482287300778893842815759530846205232156182992358091272983916094652579807955043853979954409061283384587467043725886286426326535350173010586013696341936827821361468257086837893286866641329831584849311685239231047080598926274956801391365909326134816704615666349024253151574364595787742250740736703444649421961380835355461321941396628961698396255342689806858814159438833864973322123957838932609511979119036355622080116207169408236078132338618192621194018864460463679797120855455929926504036881868630529136567351985977346077928752014817473152034277708419507133745348324612115184070176829417588536044405189281077765644762101521203776185772904775208991628430450242806638386720164651345540883866531317220374400245895237722057058752775404249072181511003489916960758180592502443016059272797557130121814119426758330502898734417372701321641037476964607825475167694889922420831642766030422193759881859581502611228370133117036922422370326445653519621910709023921218244474458576435060139572819488755551729946943134417934102755773407545171482611780326260313382025155428187799170079594914491229924057591084354076967407319868815284342574250708303648094952515756272780869064041576959272597085002301301854136167753245507656944590491777648057011304741677764525083908199535172114107795063682631882414356288857145535618231917258188524302839411296431173286743673448778890291104447112833220641415720479286910183999444993232536106092454000564537298355090214456131212879926999695391074911616111525936968168169114674717510084763921227407620378572814858027454952889564126159719299674229815251113014776530310268487597796067692047123469687012805293631748609918678555774337210483173684883821838939959476624620498177775378724366056097960448556347331436086360979699476308361987982791440692228218369619297508169036972119596315969806893735078438757936368362613354083852994290252645722957885585979446758809510261606258390132100952371639157682594957398852725932344418817644557983959003010399306188101214344324765173664041553812644957137583419901682924737246096266034105409091686490277283172852064788099264364684169656750376883092252129524055343347655855727856957476101031803989822304530843764717491178364932361587721523835221916708513558609504975863923729497182214962540431313384201032152850329801232769071244933112394909921433803702357991464025444223074125877562159897053358852255363037641836380140790490430669038532917959229360839277717537248631642247843741138299656322591642443384260688454022701326696505079142511341898384782496052957083195059792428880671707846759343333815289217737415447419661522270062155301999787671799482646137544089081340909581359017430841529437736778545339365384534232670220328224736065802051790094265832131035069443405692599582890964274443200703920809298474987169945373637131786771809655635978982057623550893379691969471815529250732685239564138147334787253557939652149533428708838372966167920515869454170237688317814460327994289851493157791558191893835253656377958417672565614404796233212475983950027696004946938288185058431380039636442298415209625322034647533461625972574513853560949007641387515926616241951554520698351663035300707091872709527368854595515886054402869570122325616007545131539165527647284034705725585627754402312687042536995225636718265617719412539597555289260514570444723337787935887649201643459223832115139640324745737115379323655320668918904079137497748266648276563295485844771912830032723929985388709752684852674684477404499345829710618235679480286328091586015647038649369175278496606304045882973932619883443047652445805402909063550990467900471947668788229612855735858933488408585013557332058076622031107395796376287644844741581923916069723388645206904394398113192832482183810858212338618976319385889652911756659405436106423906137527217875843199610494626888210757176516228493554392183450020351691258619032488106319426421900956212704850230592438162678771551208927997575886599607334281544053746391106275542385752811154247922622186011614530748977075813752859418392314144311392181989348803127574708446161551487975646949509743106382850808355291187275553182091598913839109249755202839090715944903256491223801792066990442008695560899943134112219214770661936924374942790683807082745209779603170288175838738303794840272033512527623387127263644256749509220065799282466333704656810393195603311349845211964319071092679580637689916396199577185359260419299293274957872661451267233550164529035558474739204660387721165003783281598304236853951378994407869185376720825859004637874189363919356341834944424187686665150162500122226460305869171310508735827777615300710656902007651877728662198828343548560816191648041296724206447788334237290635064542854133386610272293427647006965769180057657656087843406692001981758439840363298004189790207520370365146886324645786817068104026232676035665195583746420323955870210595399581604364276887500571683629838036543718393101349814377600657076973999739074934375564690021563634918700297598870029048816734492928136757048074792977648844439071732938853166632588774230489302407011550546477630269535484061832001962929380149269755065372189736659150912200260605862292022457370850903043153230647152480776600582018948785775416532335036032230344277836448927998318128622407546008736119683082788440538952501065299251914036601511490935918947738450511566766114540042884130427160554410085112007623902178498975687653231914037761227626273456828534010615240363994519543961742959851890987926055105323926285930184762288381456230026491195854401637163655867475307564083104526937728029941399869369437001525978970018017941627309594235887076042986027539792634637316295930793206056827829516210726187788026066737236859343370213455520372748694886263695034607325904496319218029349381352002919394911330400343410471044368106692110708213701822980706556378386729356884797736574159756428687996471797609439026720723613815298491898431586302554020250927603024350887166645558793303110594085002561757896699594239126786538686254813476740703161332726480536809255503256416306645437387685859041936159649114388749955654668571481007027922910953560010478818772470776780931080766103725896608801910698140440636414953934787920929822782401640535054867664667688082705824002620924882256155882882072069595509407450993865535217547520223183221712357182730096350460712419795462099062931090045478455312473472629709175691481914785220944673377015150467304780226263525040907110353332396952224996203082709412558491904854556563460861633369023627795494142882778275435172710112062304977822363313248312296548006692114813138461087414288024028824623327571905547474108904327224799661188538522742314918711163492068609999222761606938702785168465866261500418166423833717530808362639096703362719049455592000807519080198922392141609172230485179835634213051630346838914857240695608244264576783421592851368648297999726853013716934593501705885102539296954107491873000357765147150272787913282146056779728233515254354491409015822791883786287627848877879001971302293143024221807299525466332087288093872706378710574998030038283970747375640672599197059147095356017054219393225708170319059983926642761150724795619669486596562096976066389314342446428633253559840408352786475200104846110256414232737798383669568253854609239025533232300997846526707636052805080280389930641936157741493849091576672981532409170685885095852645776205747146506203829003956353975531032027336050932794573699156684183909338110216819001128663142544584491804715432902184071908088968411854748537487285807637265750999880071370787271033170552382859885287281678061038122918125631871485002588814862430021593460963083911500404556760854578355242192093595937240742619145437501706148897309236989250138705858689531466300284423124405304279688003251742263637571072623291831979898616736423089895421924089601004017357694801528017584172173370263469783619418347243623713509312412433821366232021888421144510524663649999385161051663584803628206750242175482100542387971295277255548351947212991746671140995429764667630391927541254542029638378767252608205442738771650779621693858430436276197405044058662497038115174671799035924110895037417950698503201056367165300866597541981119543442063671092390416863861423173373893215292347560854788140738001273901481574746622231073416317681267163136582315253212353533181544226758436391183582590440491335603704787710710044988116800191656533449205226095777293394577769358763621009816520006111624762625590721824689238274782887891442448103477307439178654661439704345748992218279589545539787418565312357693273165751435966669343944864161779240553575743879752271737673494363117311701515307671990522537557605602567195204244782312402379613858116740575134434646869690555002222376663322934646725451537639681930794499140607262414649677130845676566493174326519157313097425289022173796160544468082160197097563673934688869627253668593301487125282852757108807110824144898965126118950289467862930204610012791858719014430041296589648534818612820905282420077914036935897349976080078213001064657773765655538668947878412421330810173775006061348760617576553017727274471344804597133586808589406634565282848933070309854646212332461652724312694854179889103435170954577671791322336934330703319954356948234781623475220154669726929216438382210072676917128228982298700856736685898839313626109674028164503037499295519569649879238852432359502465833930033212791119392903294023680175705643174179752370428687113613858701562195576543309085838323409116005310319006026089724876341558561990938351114197241721246027596879004334621303312710438523839422146854447401756448687554900115054674426009252925161191926653983287274523787841507403236508750149410923362868096729059192491826422281455926832964355551197574315759980940849786681630351425032982711046319322924639995078647644590376719702010197296402585595619445625493160069287198157694203078181205896276832164920229145711143599230452600903507714990534130799777299648803603825091523042646456942312322836101185212913664667616085635766118410255390990807978162234565696520269939178674619853730374482035013422713048720674616267701123945665594426844783197083827423189524755362750620826870457070362512467399875057205131937977565748765124224587951633326414834625149799804148945010142863557770498035820502802004722234199904418038199381185692851658452249525874279633200002766663646327057096483053545902925007116604180716251008510054826632993636963725892305682326305876950046853175968096516907993014671827858096264595486025516925146542803819712217223713702830286754011873379839126747854997828991436467757489828175164671698157261595489873285938979557958029621731304766538750403507098894135639738871070513245999151055155986337529989034174893499644580511931795536531506799964153929979888690416611492712242320878745599857899168889528832586442401542657957493802969154212351319664737802328237713685852700687751139697295848414424678433490833676497213927941073778613996801809320844302669141503710546762940140896678025184797668912851482720732412575549422042991395750217595647007441347861009641093327749706902029095675308185478426343261870011880764998615069015798749279157270476996452780758167557049626728033518403108602081604209599542624309189541092239592742303038125693017668964576928416047586657640610761669476330797960784413955460509021238686050848509872573303773494885679042283282809798752440795351878394177791785474552951534642918520383370714636192489620177355061896167263304359205775266337767674563326091442139698878123260782640498425090309490600526249261025091059414430833065152252921203602988555244612921697704441951036012918949993452908024582653431884754709742873514796050106774390328073591931866888415151224765577385194950339804424060619006720864718281223784862322020624510703384839758480772384310079849147879946158661853778242907356215334453460020173050658680639028114185289845838451697753464276072439240484945738294972222563680835562064966858512307043149231591731017520097312513507788966158463260150203090615865932824411840901933848051424004680560683549047625225783854352711205380899003893163022470594039768882794378928369480115556254825256693469139582562872016159162576938267829265744429944479481101388950075456250605745218955605506033579306272196984206834967002673837791112610143958974015947485756601874880530664895143310222661401432237915698423747975078779622163297572499134045394004996989287988105623162826942740679383903048877550125166219522202922586754743430443208420931498831809655379546975864032905153496757310029897999426668652122954454537364908762875437021697474034702359393431635441908274509104898838257233360063023347211786677623994410791683079070954184449894702552719175536870604694362478366422608098239505305058220720171886076465303073072257616815029785221501290801580986631485064353338078008201369985611979038135173929154155996943088879233768766384222639002054767586514513992913352085659445323934296731460472001416724834987068548619716184589671607992188264135245068714530521338832493942909061267573640853003435023197233994614038239496185170292703308065762905888987902964211937088076172134454311536184610802276200314039332357346766549702836139786743515264929271248036466036707888528874949367790111747527788193619150913701363315206847752367982115660628556989308661699278209998730561494526546468866593407168293064750093589212514249677132994278222742415710429691684895015188728260164015091328622212042154907736938828353654419010233496350428843153850893303119341130950828372743494205521573504707073252632425260036347074122030756816508068552049133263000376679687281512904862539417817453932247124393025663298245317804741748782180671749787352420850666512496140042818126334505744261573685080091200619617056112389895999735910244023587776408451668747734468673394265027771828720180967970806290032121679146813014704710864572171153967180759701833401250389031910831674518628096997459520048553769616120975712224686531388301674178497505421121397062020170593115493106883555126068938888332021908509354828985572658238447089264673475786886883384996316295850110604817230011055181902327848340295374664553127628184004633886141358161615236365822361926485023293085801149922887842502046192134138789913836942243766825585721620076009288021436465452990165912198022377234510041760200718141256422478646638347135125353752728641088262342512802795353363399447350200168341682341561433056840631104666463756431103887213057302807860736086631185032569188639637802706153438196707505264783678924257799641366325176658582106433481041383432905921872672211584972583107666423262602911793945175604941340914551020557748647896948883197654193243469859443397959375957423012966598336664039795882474291711905602213440503031464435747481429139929001959147338822175634148265444061552861493787620157086426017020975086229423505233999222260907504011476536488620775379960334136736393775044460772935086904153572577837734439611487155775939979971678000252074750432066307116876959179259652217270468591167837912250749210651365952563694523112657699135669128278937457759511621627612834022193908355618607574134626464536569085400441286250914481952072168219163343279368552695684071370875634695921172640938981625857322983515388044365005909044814859916410599862465237882137156372452243251016658409886482001795255391201943624968077029901613706410739300737704584705571658845610357551699720588034816718313633035771646783190931241068127431652840391980412219913038122090737316739127477592035214011625471743010618051094349230181873073329701509129330205703016749087607198070842358275302896513759291220273381707437776582591013325852015651852523103964085880833772672472978962265093095932042656530470525112416616462344132914465341473603618654128762954513936084354165336074018267533389197726860577942558415567326982392202581579115631846248204324251515394892304345174796181090392791380179018791065687089745145412051341937676407460597122355811083894929360677913693954442258670451230850547349176750117470026879352462472948381831200329355294251315408928935936751216877829444318714256572326297001507783824379867165441130468146259818947821470360013162850786354144024136788293496568021717556561203723868416371466202624738974076122499442311169552194275777372945001300648661671375149495058507346036612327324743274926574173309599371491363941621675144693984154055168173394498341636613299685706114297982514269037971106160664385011142141474636276977774920906825380420176764767948571032426237005304598615172095202856224240638116678439900871688690525138051668207931361571128265125046452109631782562526026720244605329344033981447578624490123793874026145323967127557585493016932530661408030679448932858081153022947256127636888925545641996672373983599780057772584674771948978090049311667106033840530359482176595239867009498829006748978116093853985965007907347180595419202827130142559732515129271776059839779584138597527174085808966325991662933868366532649639607383413040724675625249830244973540028236902767500928373169945635870604263064875506368752508548728049112081768254758275355920314722034223845462420266085186408715193642778170990439641636479479805468568461934445111203831845345747711895541498561629368353951750704217104491520726962366788468347946950534011556244715361077619901150300087204786379461357140268186364206138945876538652084260125433426262424873574606903216576765273369317708378589308186633440614322678985583032830461399507082296316276293316180495323823158087735522931976099671136293067469491713906119099271719891074899674061588322181904665364318278723099335521960542277289519597033252744140563808072421502573588908745477680338112668665354965162707623665950337218201164324136604699606763997741478314804302815467072297886662772487537982051872291057059732802935355148110002722612550242674538719658524736032417955297047801350955702141850324154914149635102295870544086009272541284051553149345847003221661437500271798015692088700063734621803219894956835616780783114571672987845089946541434398438695279869044636066789728197576159156815856776630922796631827336122913657809542348680312935815085098595587225602944955955997684119318171792813244279072468309489016583571678639382134351948517582219283170665565315298228889131103088200064943347986659369014878466810616377290146081282283096659717718928548684046443095459304513079015520555450916248059209432286454217099007571330326580741981871417857019292885859640788399554653720025127609035326010245919276359319696218029447484328870870205424985988181531302679607233112416242070040481867750068140561046275619183181020606321130162620240247020824426348193084815545789812307339822003403502042605488174725761125286218892367498553784490654912228615974472966298940910712166465095565091476044170869786593462811571201492330088303972718129162909576380268311971448454789929332834122512395656272507315999210585504304313793575742952685550158097479783996376991871563332196338952361331302357159954893683551866533132922083052532940207909533168800090907192941085813525454209044182022727616572194795825858232205028072326070333686702514764676380368289012582434946727645192956092540644151612688611101178400733098519189733146942836627728153656577164951311515143608598097186609231134859388901309827415478300174472033061239054309742620462837014820696931905589383748167264294223693269845223482285234355868610647327472692763038030051568575843313234047176480795251359607551251857402429578157093658868246475966876154375787296922608854439242750939613210877953378443002232594643281099884683974696415970174740201384074724150724800215969402038150983997228025917865096473646597992716478467178456670234733193117714691396591710320657906748561844630027504516558451118633715599962299533341894343843552953930500318994387102345909695517516045503649469414478805629608204135808092670078563878854878424087201485332374516641377857904072730767479015057376455914494290895159909694484196246390213286248411468940667749463652993053701366470609156927757403035238757130884267857452998826096028902220644124815691057737882569405975828423765500799097300067118555156761235135740756285890217777662097198090394376867960369086249742433285089262980145541260499816429918790905458095224512137457743229217327741482561316397084249136898629554989412759821476861407165062539649121600719649592387116187730624956818452818763874887955258941399573296731050013496891892654880663474985205267729072154789215087499594747390939661252107245440313428003362580856333692395068307787679157889397133622107403121703658158821540362613094787128522092152624861424324843948441071378856238787904736248766201184983133734934425877978702280126613761528779227928484156710815752722864778255678081154432806492453553617991308413078680574572199621006939355939568407494369986493840026591613491601394924148691859376477266596299433469922114919995963014227645601310289023590680436317947358819796844951003710787322103176316073713092046325006758390190413237545091914024812838111096428068864754519807664805251884612140326053587808092856757964542074340280206791912336235410096795001471962862983627355882287195887280432686043364077896129612015719433301145215486279271895693351549005253974311123694012632692622344957600491395810978003669942618973215131722744463089217292815959005537382691192575329345079172975158332611672701045961810495238286066078709758552118180335814848241464708811100425756492547075785479849595985094026007577049868248961046323830446954007440993636387928764361491808639343144941017032754850338901531481745106645223275664389546252612358888531070052643063746637156536188456829262577140957597299185759740145619637081100929417983817883258209612800867243900973797715728580421203698650466813762522570867428584861002538847190536483882554862728704769621709130706613498004671610074066172868079453042983856696533715567613382315894528226265781409177694354483570923964918638616265151332304430166212716945778058630993781331930845422843895510397231397808860305456499325911948702437728436903363716799682828750084257299720083842825403401097806382009236960822980953551967964501395800910698317239548090102733814280228317299901525530177959473433717027785687154145182347067812887847231651755712931940096663486883069231754142544376612083063052249623727175390877451723688886663195728209350208165971276801645710169433463339554983061916188608118146941290059692379028422654944834237061530954769885691009076355234890800678943308319325739187154438730124237345236525766347702741083265287141264816912980213189020865709753108637868649614693044328213686635517325744739500178276988239475966843917951177384530166121374622389471825701874623819878087967561933118849579741725597903483826299504124884579575155195588057876588941880044163513137322624755670790412278097794663406006326715667126580709903365810734926058682294318846047469240833045425372118025563760032454829435052824801441583552137371952789015893612308979328357073662887055560389274069624353199849283696479527595967207298121946646300256407527059636117812985961447186720744019872731994239532498539010348728120079734199112632920766861052608054808504146042259059844608030208332340673397134827426017893142796724004014301403436410720121355791773359054324360960326385845025705023483432349803798696517617737942758475702597586707804139537247593843934950686308344878983797658531085625987022087293041229565962787863734452428558564988977001475128360626960533202780228481749631622619381170997485759630423354401919599172436037127613921209739833208534859253072734829142598233540325160811529350837273393714135924054850698399470781204968685663582522614223070112171943832920091487850164354871523957625816976690097007759192208230068234542548023998233165373773972841095678340010257619211156390244989392350843431860561856926063178470922040978267942965553664412793909763019052245954084553920911814413461716179707517091689750884103548821198249227523150703880952657187980439543672609864095955850412866154819966061963208610418860724991612745991425589683071235282650028300518566678165056973233089498096929858052613634024445002353862946788417077473287872972710560941013445438594021574860846531248092915042596052235289993175920733565602152872985852880538807656043053965633169251369395705518172356893160639674341595558930431558450964919144051108383968218079334604949487319052247537780243926975646187780052055319419521893640865521136056290116192597117860277575402952692427330280558172514773443297853924098992989441895554745209354360990166560309296888913942660351113350301962965540449965528980816445175910569327268613375683962399549525742696878538292221650095776200866207597564903532731912990154566908687594739507025719220566640878874816849627655934146168801378457001184578273329341135885715590087739823461236421930642394636075831622397069843085186307380808359041319352248947892960006598168005962141908366671173284067255324397089009222680416729636057263070884061245753452501307687957463806671543386965698225049227951344007519068037818242799277025485762316530304445190805414449836598845352451679190001408090835934777143071081276109319390119940322220634350780701959449861701615022953547921305323862538234162035513606219339362415154782242084694397218962781268638671844861776940099091340251318641959020788975502449108825391229467969681288999502998058511767088106734086310277638007579166982729254891998559058356215880177483082802539799937773018225410222611712479345759807206552566387310243511451358480566062328039222282208612327378988670206658635906329683858291602765145687463437769188783034524506104689444962052423787838278544490828662350297024332544815172761026987768006793921681632936840231974734940522064782912033257999680016922697491800165349917426934469351474008772285271200325795996142556532547225105990520617823019052886113681857967137384913684723432618343773133107387429692694288499413109377463185802880569007581484444458224527177503149093766970651748972199641017935412834022651632550005192643177458611987737923071825460669908296587118023792299350284694183963471948207340094792970309628802098951323711320462352086031247087585167970522754329494477084195495176743044901064257095415138765072437296762581644072662326118170476028745009177111747151558569893652718268734312901685292617221570373195464984244561176191234506923371704730183820138133054542808951662207333521778896655647592042500099585338972573906310011338890658358266875491945685095586784162825143105398115810816566061206581439263686639014278298929786092626985477039492140531453083378843715822516080813432756229697704957444484518882710297535908966513936364283879020315020050022795840704877984354431447969162215705262174860304677153582658368529851103609683408047254444192890696857700799818822071336991480991912808190249663465088543607711508338243000007660622201789785419455219893655896617747088162363136510075737710999168253640830672309404666753936954549487925385024618150092468383505918958243016731417521979532411058847135451563701055349779955184425142412338779927453282984609939239221552389613753719304755730291830802260854211393041146180072824766752157061430218849913528391571854553559008336102169251107965705554067011772592340624798971390930990608581185533832129679648291657825205222249426823112729267786935809613469804679703506109544330769782445347037741787532292145298642704945424794798034409292703887567640001001674746516613109054591362131984669446605321791833797023969989276265334528090420552005309015629915470040902664368632608774364646869760667770939268846246861143700708940713613357334915617008982416422857964038274243956211202726456929719908545388785488665360155492882248364911771094734E+3371641036578