


'''simple docstring'''

def __UpperCamelCase   (			__lowerCamelCase		: int      ,  __lowerCamelCase		: bool = False				)      ->     bool:







     '''simple docstring'''






     if n == 2:
          return True
     if not n % 2 or n < 2:
          return False
     if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
          return False
     if n > 3_3170_4406_4679_8873_8596_1981 and not allow_probable:
          raise ValueError(
              "Warning: upper bound of deterministic test is exceeded. "
              "Pass allow_probable=True to allow probabilistic test. "
              "A return value of True indicates a probable prime."				)
     # array bounds provided by analysis
     _a						=		[
         2047,
         137_3653,
         2532_6001,
         32_1503_1751,
         2_1523_0289_8747,
         3_4747_4966_0383,
         341_5500_7172_8321,
         1,
         382_5123_0565_4641_3051,
         1,
         1,
         3186_6585_7834_0311_5116_7461,
         3_3170_4406_4679_8873_8596_1981,
     ]

     _a						=		[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
     for idx, _p in enumerate(__lowerCamelCase      ,  1				):
          if n < _p:
               # then we have our last prime to check
               _a						=		primes[:idx]
               break
     _a			,			_a						=		n - 1, 0
     # break up n -1 into a power of 2 (s) and
     # remaining odd component
     # essentially, solve for d * 2 ** s == n - 1
     while d % 2 == 0:
          d //= 2
          s += 1
     for prime in plist:
          _a						=		False
          for r in range(__lowerCamelCase				):
               _a						=		pow(__lowerCamelCase      ,  d * 2**r      ,  __lowerCamelCase				)
               # see article for analysis explanation for m
               if (r == 0 and m == 1) or ((m + 1) % n == 0):
                    _a						=		True
                    # this loop will not determine compositeness
                    break
          if pr:
               continue
          # if pr is False, then the above loop never evaluated to true,
          # and the n MUST be composite
          return False
     return True






def __UpperCamelCase   (			)      ->     None:







     '''simple docstring'''






     assert not miller_rabin(561				)
     assert miller_rabin(563				)
     # 2047

     assert not miller_rabin(83_8201				)
     assert miller_rabin(83_8207				)
     # 1_373_653

     assert not miller_rabin(1731_6001				)
     assert miller_rabin(1731_6017				)
     # 25_326_001

     assert not miller_rabin(30_7838_6641				)
     assert miller_rabin(30_7838_6653				)
     # 3_215_031_751

     assert not miller_rabin(1_7130_4557_4801				)
     assert miller_rabin(1_7130_4557_4819				)
     # 2_152_302_898_747

     assert not miller_rabin(2_7797_9972_8307				)
     assert miller_rabin(2_7797_9972_8327				)
     # 3_474_749_660_383

     assert not miller_rabin(113_8500_2390_9441				)
     assert miller_rabin(113_8500_2390_9527				)
     # 341_550_071_728_321

     assert not miller_rabin(127_5041_0188_4880_4351				)
     assert miller_rabin(127_5041_0188_4880_4391				)
     # 3_825_123_056_546_413_051

     assert not miller_rabin(796_6646_4458_5077_8779_1867				)
     assert miller_rabin(796_6646_4458_5077_8779_1951				)
     # 318_665_857_834_031_151_167_461

     assert not miller_rabin(5528_4067_7446_6478_9766_0333				)
     assert miller_rabin(5528_4067_7446_6478_9766_0359				)
     # 3_317_044_064_679_887_385_961_981
     # upper limit for probabilistic test


if __name__ == "__main__":
   test_miller_rabin()





'''simple docstring'''

def __UpperCamelCase   (			__lowerCamelCase		: int = 400_0000				)      ->     int:







     '''simple docstring'''






     _a						=		[]
     _a			,			_a						=		0, 1
     while b <= n:
          if b % 2 == 0:
               even_fibs.append(__lowerCamelCase				)
          _a			,			_a						=		b, a + b
     return sum(__lowerCamelCase				)


if __name__ == "__main__":
   print(f'''{solution() = }''')

