hgcd_appr.o

hgcd_appr.o (text/plain), 172.56 KB, created by Justin Lecher (RETIRED) on 2013-03-23 11:23:53 UTC

# 1 "hgcd_appr.c"
#define __STDC__ 1
# 1 "hgcd_appr.c"
#define __STDC_VERSION__ 199901L
# 1 "hgcd_appr.c"
#define __STDC_UTF_16__ 1
# 1 "hgcd_appr.c"
#define __STDC_UTF_32__ 1
# 1 "hgcd_appr.c"
#define __STDC_HOSTED__ 1
# 1 "hgcd_appr.c"
#define __GNUC__ 4
# 1 "hgcd_appr.c"
#define __GNUC_MINOR__ 7
# 1 "hgcd_appr.c"
#define __GNUC_PATCHLEVEL__ 2
# 1 "hgcd_appr.c"
#define __VERSION__ "4.7.2"
# 1 "hgcd_appr.c"
#define __ATOMIC_RELAXED 0
# 1 "hgcd_appr.c"
#define __ATOMIC_SEQ_CST 5
# 1 "hgcd_appr.c"
#define __ATOMIC_ACQUIRE 2
# 1 "hgcd_appr.c"
#define __ATOMIC_RELEASE 3
# 1 "hgcd_appr.c"
#define __ATOMIC_ACQ_REL 4
# 1 "hgcd_appr.c"
#define __ATOMIC_CONSUME 1
# 1 "hgcd_appr.c"
#define __pic__ 2
# 1 "hgcd_appr.c"
#define __PIC__ 2
# 1 "hgcd_appr.c"
#define __OPTIMIZE__ 1
# 1 "hgcd_appr.c"
#define __FINITE_MATH_ONLY__ 0
# 1 "hgcd_appr.c"
#define _LP64 1
# 1 "hgcd_appr.c"
#define __LP64__ 1
# 1 "hgcd_appr.c"
#define __SIZEOF_INT__ 4
# 1 "hgcd_appr.c"
#define __SIZEOF_LONG__ 8
# 1 "hgcd_appr.c"
#define __SIZEOF_LONG_LONG__ 8
# 1 "hgcd_appr.c"
#define __SIZEOF_SHORT__ 2
# 1 "hgcd_appr.c"
#define __SIZEOF_FLOAT__ 4
# 1 "hgcd_appr.c"
#define __SIZEOF_DOUBLE__ 8
# 1 "hgcd_appr.c"
#define __SIZEOF_LONG_DOUBLE__ 16
# 1 "hgcd_appr.c"
#define __SIZEOF_SIZE_T__ 8
# 1 "hgcd_appr.c"
#define __CHAR_BIT__ 8
# 1 "hgcd_appr.c"
#define __BIGGEST_ALIGNMENT__ 32
# 1 "hgcd_appr.c"
#define __ORDER_LITTLE_ENDIAN__ 1234
# 1 "hgcd_appr.c"
#define __ORDER_BIG_ENDIAN__ 4321
# 1 "hgcd_appr.c"
#define __ORDER_PDP_ENDIAN__ 3412
# 1 "hgcd_appr.c"
#define __BYTE_ORDER__ __ORDER_LITTLE_ENDIAN__
# 1 "hgcd_appr.c"
#define __FLOAT_WORD_ORDER__ __ORDER_LITTLE_ENDIAN__
# 1 "hgcd_appr.c"
#define __SIZEOF_POINTER__ 8
# 1 "hgcd_appr.c"
#define __SIZE_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __PTRDIFF_TYPE__ long int
# 1 "hgcd_appr.c"
#define __WCHAR_TYPE__ int
# 1 "hgcd_appr.c"
#define __WINT_TYPE__ unsigned int
# 1 "hgcd_appr.c"
#define __INTMAX_TYPE__ long int
# 1 "hgcd_appr.c"
#define __UINTMAX_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __CHAR16_TYPE__ short unsigned int
# 1 "hgcd_appr.c"
#define __CHAR32_TYPE__ unsigned int
# 1 "hgcd_appr.c"
#define __SIG_ATOMIC_TYPE__ int
# 1 "hgcd_appr.c"
#define __INT8_TYPE__ signed char
# 1 "hgcd_appr.c"
#define __INT16_TYPE__ short int
# 1 "hgcd_appr.c"
#define __INT32_TYPE__ int
# 1 "hgcd_appr.c"
#define __INT64_TYPE__ long int
# 1 "hgcd_appr.c"
#define __UINT8_TYPE__ unsigned char
# 1 "hgcd_appr.c"
#define __UINT16_TYPE__ short unsigned int
# 1 "hgcd_appr.c"
#define __UINT32_TYPE__ unsigned int
# 1 "hgcd_appr.c"
#define __UINT64_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __INT_LEAST8_TYPE__ signed char
# 1 "hgcd_appr.c"
#define __INT_LEAST16_TYPE__ short int
# 1 "hgcd_appr.c"
#define __INT_LEAST32_TYPE__ int
# 1 "hgcd_appr.c"
#define __INT_LEAST64_TYPE__ long int
# 1 "hgcd_appr.c"
#define __UINT_LEAST8_TYPE__ unsigned char
# 1 "hgcd_appr.c"
#define __UINT_LEAST16_TYPE__ short unsigned int
# 1 "hgcd_appr.c"
#define __UINT_LEAST32_TYPE__ unsigned int
# 1 "hgcd_appr.c"
#define __UINT_LEAST64_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __INT_FAST8_TYPE__ signed char
# 1 "hgcd_appr.c"
#define __INT_FAST16_TYPE__ long int
# 1 "hgcd_appr.c"
#define __INT_FAST32_TYPE__ long int
# 1 "hgcd_appr.c"
#define __INT_FAST64_TYPE__ long int
# 1 "hgcd_appr.c"
#define __UINT_FAST8_TYPE__ unsigned char
# 1 "hgcd_appr.c"
#define __UINT_FAST16_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __UINT_FAST32_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __UINT_FAST64_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __INTPTR_TYPE__ long int
# 1 "hgcd_appr.c"
#define __UINTPTR_TYPE__ long unsigned int
# 1 "hgcd_appr.c"
#define __GXX_ABI_VERSION 1002
# 1 "hgcd_appr.c"
#define __SCHAR_MAX__ 127
# 1 "hgcd_appr.c"
#define __SHRT_MAX__ 32767
# 1 "hgcd_appr.c"
#define __INT_MAX__ 2147483647
# 1 "hgcd_appr.c"
#define __LONG_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __LONG_LONG_MAX__ 9223372036854775807LL
# 1 "hgcd_appr.c"
#define __WCHAR_MAX__ 2147483647
# 1 "hgcd_appr.c"
#define __WCHAR_MIN__ (-__WCHAR_MAX__ - 1)
# 1 "hgcd_appr.c"
#define __WINT_MAX__ 4294967295U
# 1 "hgcd_appr.c"
#define __WINT_MIN__ 0U
# 1 "hgcd_appr.c"
#define __PTRDIFF_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __SIZE_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __INTMAX_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __INTMAX_C(c) c ## L
# 1 "hgcd_appr.c"
#define __UINTMAX_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __UINTMAX_C(c) c ## UL
# 1 "hgcd_appr.c"
#define __SIG_ATOMIC_MAX__ 2147483647
# 1 "hgcd_appr.c"
#define __SIG_ATOMIC_MIN__ (-__SIG_ATOMIC_MAX__ - 1)
# 1 "hgcd_appr.c"
#define __INT8_MAX__ 127
# 1 "hgcd_appr.c"
#define __INT16_MAX__ 32767
# 1 "hgcd_appr.c"
#define __INT32_MAX__ 2147483647
# 1 "hgcd_appr.c"
#define __INT64_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __UINT8_MAX__ 255
# 1 "hgcd_appr.c"
#define __UINT16_MAX__ 65535
# 1 "hgcd_appr.c"
#define __UINT32_MAX__ 4294967295U
# 1 "hgcd_appr.c"
#define __UINT64_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __INT_LEAST8_MAX__ 127
# 1 "hgcd_appr.c"
#define __INT8_C(c) c
# 1 "hgcd_appr.c"
#define __INT_LEAST16_MAX__ 32767
# 1 "hgcd_appr.c"
#define __INT16_C(c) c
# 1 "hgcd_appr.c"
#define __INT_LEAST32_MAX__ 2147483647
# 1 "hgcd_appr.c"
#define __INT32_C(c) c
# 1 "hgcd_appr.c"
#define __INT_LEAST64_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __INT64_C(c) c ## L
# 1 "hgcd_appr.c"
#define __UINT_LEAST8_MAX__ 255
# 1 "hgcd_appr.c"
#define __UINT8_C(c) c
# 1 "hgcd_appr.c"
#define __UINT_LEAST16_MAX__ 65535
# 1 "hgcd_appr.c"
#define __UINT16_C(c) c
# 1 "hgcd_appr.c"
#define __UINT_LEAST32_MAX__ 4294967295U
# 1 "hgcd_appr.c"
#define __UINT32_C(c) c ## U
# 1 "hgcd_appr.c"
#define __UINT_LEAST64_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __UINT64_C(c) c ## UL
# 1 "hgcd_appr.c"
#define __INT_FAST8_MAX__ 127
# 1 "hgcd_appr.c"
#define __INT_FAST16_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __INT_FAST32_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __INT_FAST64_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __UINT_FAST8_MAX__ 255
# 1 "hgcd_appr.c"
#define __UINT_FAST16_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __UINT_FAST32_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __UINT_FAST64_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __INTPTR_MAX__ 9223372036854775807L
# 1 "hgcd_appr.c"
#define __UINTPTR_MAX__ 18446744073709551615UL
# 1 "hgcd_appr.c"
#define __FLT_EVAL_METHOD__ 0
# 1 "hgcd_appr.c"
#define __DEC_EVAL_METHOD__ 2
# 1 "hgcd_appr.c"
#define __FLT_RADIX__ 2
# 1 "hgcd_appr.c"
#define __FLT_MANT_DIG__ 24
# 1 "hgcd_appr.c"
#define __FLT_DIG__ 6
# 1 "hgcd_appr.c"
#define __FLT_MIN_EXP__ (-125)
# 1 "hgcd_appr.c"
#define __FLT_MIN_10_EXP__ (-37)
# 1 "hgcd_appr.c"
#define __FLT_MAX_EXP__ 128
# 1 "hgcd_appr.c"
#define __FLT_MAX_10_EXP__ 38
# 1 "hgcd_appr.c"
#define __FLT_DECIMAL_DIG__ 9
# 1 "hgcd_appr.c"
#define __FLT_MAX__ 3.40282346638528859812e+38F
# 1 "hgcd_appr.c"
#define __FLT_MIN__ 1.17549435082228750797e-38F
# 1 "hgcd_appr.c"
#define __FLT_EPSILON__ 1.19209289550781250000e-7F
# 1 "hgcd_appr.c"
#define __FLT_DENORM_MIN__ 1.40129846432481707092e-45F
# 1 "hgcd_appr.c"
#define __FLT_HAS_DENORM__ 1
# 1 "hgcd_appr.c"
#define __FLT_HAS_INFINITY__ 1
# 1 "hgcd_appr.c"
#define __FLT_HAS_QUIET_NAN__ 1
# 1 "hgcd_appr.c"
#define __DBL_MANT_DIG__ 53
# 1 "hgcd_appr.c"
#define __DBL_DIG__ 15
# 1 "hgcd_appr.c"
#define __DBL_MIN_EXP__ (-1021)
# 1 "hgcd_appr.c"
#define __DBL_MIN_10_EXP__ (-307)
# 1 "hgcd_appr.c"
#define __DBL_MAX_EXP__ 1024
# 1 "hgcd_appr.c"
#define __DBL_MAX_10_EXP__ 308
# 1 "hgcd_appr.c"
#define __DBL_DECIMAL_DIG__ 17
# 1 "hgcd_appr.c"
#define __DBL_MAX__ ((double)1.79769313486231570815e+308L)
# 1 "hgcd_appr.c"
#define __DBL_MIN__ ((double)2.22507385850720138309e-308L)
# 1 "hgcd_appr.c"
#define __DBL_EPSILON__ ((double)2.22044604925031308085e-16L)
# 1 "hgcd_appr.c"
#define __DBL_DENORM_MIN__ ((double)4.94065645841246544177e-324L)
# 1 "hgcd_appr.c"
#define __DBL_HAS_DENORM__ 1
# 1 "hgcd_appr.c"
#define __DBL_HAS_INFINITY__ 1
# 1 "hgcd_appr.c"
#define __DBL_HAS_QUIET_NAN__ 1
# 1 "hgcd_appr.c"
#define __LDBL_MANT_DIG__ 64
# 1 "hgcd_appr.c"
#define __LDBL_DIG__ 18
# 1 "hgcd_appr.c"
#define __LDBL_MIN_EXP__ (-16381)
# 1 "hgcd_appr.c"
#define __LDBL_MIN_10_EXP__ (-4931)
# 1 "hgcd_appr.c"
#define __LDBL_MAX_EXP__ 16384
# 1 "hgcd_appr.c"
#define __LDBL_MAX_10_EXP__ 4932
# 1 "hgcd_appr.c"
#define __DECIMAL_DIG__ 21
# 1 "hgcd_appr.c"
#define __LDBL_MAX__ 1.18973149535723176502e+4932L
# 1 "hgcd_appr.c"
#define __LDBL_MIN__ 3.36210314311209350626e-4932L
# 1 "hgcd_appr.c"
#define __LDBL_EPSILON__ 1.08420217248550443401e-19L
# 1 "hgcd_appr.c"
#define __LDBL_DENORM_MIN__ 3.64519953188247460253e-4951L
# 1 "hgcd_appr.c"
#define __LDBL_HAS_DENORM__ 1
# 1 "hgcd_appr.c"
#define __LDBL_HAS_INFINITY__ 1
# 1 "hgcd_appr.c"
#define __LDBL_HAS_QUIET_NAN__ 1
# 1 "hgcd_appr.c"
#define __DEC32_MANT_DIG__ 7
# 1 "hgcd_appr.c"
#define __DEC32_MIN_EXP__ (-94)
# 1 "hgcd_appr.c"
#define __DEC32_MAX_EXP__ 97
# 1 "hgcd_appr.c"
#define __DEC32_MIN__ 1E-95DF
# 1 "hgcd_appr.c"
#define __DEC32_MAX__ 9.999999E96DF
# 1 "hgcd_appr.c"
#define __DEC32_EPSILON__ 1E-6DF
# 1 "hgcd_appr.c"
#define __DEC32_SUBNORMAL_MIN__ 0.000001E-95DF
# 1 "hgcd_appr.c"
#define __DEC64_MANT_DIG__ 16
# 1 "hgcd_appr.c"
#define __DEC64_MIN_EXP__ (-382)
# 1 "hgcd_appr.c"
#define __DEC64_MAX_EXP__ 385
# 1 "hgcd_appr.c"
#define __DEC64_MIN__ 1E-383DD
# 1 "hgcd_appr.c"
#define __DEC64_MAX__ 9.999999999999999E384DD
# 1 "hgcd_appr.c"
#define __DEC64_EPSILON__ 1E-15DD
# 1 "hgcd_appr.c"
#define __DEC64_SUBNORMAL_MIN__ 0.000000000000001E-383DD
# 1 "hgcd_appr.c"
#define __DEC128_MANT_DIG__ 34
# 1 "hgcd_appr.c"
#define __DEC128_MIN_EXP__ (-6142)
# 1 "hgcd_appr.c"
#define __DEC128_MAX_EXP__ 6145
# 1 "hgcd_appr.c"
#define __DEC128_MIN__ 1E-6143DL
# 1 "hgcd_appr.c"
#define __DEC128_MAX__ 9.999999999999999999999999999999999E6144DL
# 1 "hgcd_appr.c"
#define __DEC128_EPSILON__ 1E-33DL
# 1 "hgcd_appr.c"
#define __DEC128_SUBNORMAL_MIN__ 0.000000000000000000000000000000001E-6143DL
# 1 "hgcd_appr.c"
#define __REGISTER_PREFIX__ 
# 1 "hgcd_appr.c"
#define __USER_LABEL_PREFIX__ 
# 1 "hgcd_appr.c"
#define _FORTIFY_SOURCE ((defined __OPTIMIZE__ && __OPTIMIZE__ > 0) ? 2 : 0)
# 1 "hgcd_appr.c"
#define __GNUC_STDC_INLINE__ 1
# 1 "hgcd_appr.c"
#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_1 1
# 1 "hgcd_appr.c"
#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_2 1
# 1 "hgcd_appr.c"
#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_4 1
# 1 "hgcd_appr.c"
#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_8 1
# 1 "hgcd_appr.c"
#define __GCC_HAVE_SYNC_COMPARE_AND_SWAP_16 1
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_BOOL_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_CHAR_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_CHAR16_T_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_CHAR32_T_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_WCHAR_T_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_SHORT_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_INT_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_LONG_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_LLONG_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_TEST_AND_SET_TRUEVAL 1
# 1 "hgcd_appr.c"
#define __GCC_ATOMIC_POINTER_LOCK_FREE 2
# 1 "hgcd_appr.c"
#define __GCC_HAVE_DWARF2_CFI_ASM 1
# 1 "hgcd_appr.c"
#define __PRAGMA_REDEFINE_EXTNAME 1
# 1 "hgcd_appr.c"
#define __SIZEOF_INT128__ 16
# 1 "hgcd_appr.c"
#define __SIZEOF_WCHAR_T__ 4
# 1 "hgcd_appr.c"
#define __SIZEOF_WINT_T__ 4
# 1 "hgcd_appr.c"
#define __SIZEOF_PTRDIFF_T__ 8
# 1 "hgcd_appr.c"
#define __amd64 1
# 1 "hgcd_appr.c"
#define __amd64__ 1
# 1 "hgcd_appr.c"
#define __x86_64 1
# 1 "hgcd_appr.c"
#define __x86_64__ 1
# 1 "hgcd_appr.c"
#define __corei7 1
# 1 "hgcd_appr.c"
#define __corei7__ 1
# 1 "hgcd_appr.c"
#define __tune_corei7__ 1
# 1 "hgcd_appr.c"
#define __MMX__ 1
# 1 "hgcd_appr.c"
#define __SSE__ 1
# 1 "hgcd_appr.c"
#define __SSE2__ 1
# 1 "hgcd_appr.c"
#define __SSE3__ 1
# 1 "hgcd_appr.c"
#define __SSSE3__ 1
# 1 "hgcd_appr.c"
#define __SSE4_1__ 1
# 1 "hgcd_appr.c"
#define __SSE4_2__ 1
# 1 "hgcd_appr.c"
#define __AES__ 1
# 1 "hgcd_appr.c"
#define __PCLMUL__ 1
# 1 "hgcd_appr.c"
#define __AVX__ 1
# 1 "hgcd_appr.c"
#define __POPCNT__ 1
# 1 "hgcd_appr.c"
#define __SSE_MATH__ 1
# 1 "hgcd_appr.c"
#define __SSE2_MATH__ 1
# 1 "hgcd_appr.c"
#define __gnu_linux__ 1
# 1 "hgcd_appr.c"
#define __linux 1
# 1 "hgcd_appr.c"
#define __linux__ 1
# 1 "hgcd_appr.c"
#define linux 1
# 1 "hgcd_appr.c"
#define __unix 1
# 1 "hgcd_appr.c"
#define __unix__ 1
# 1 "hgcd_appr.c"
#define unix 1
# 1 "hgcd_appr.c"
#define __ELF__ 1
# 1 "hgcd_appr.c"
#define __DECIMAL_BID_FORMAT__ 1
# 1 "<command-line>"
#define HAVE_CONFIG_H 1
#define __GMP_WITHIN_GMP 1
#define OPERATION_hgcd_appr 1
#define PIC 1
# 1 "hgcd_appr.c"
# 24 "hgcd_appr.c"
# 1 "../gmp.h" 1
# 32 "../gmp.h"
#define __GMP_HAVE_HOST_CPU_FAMILY_power 0
#define __GMP_HAVE_HOST_CPU_FAMILY_powerpc 0
#define GMP_LIMB_BITS 64
#define GMP_NAIL_BITS 0

#define GMP_NUMB_BITS (GMP_LIMB_BITS - GMP_NAIL_BITS)
#define GMP_NUMB_MASK ((~ __GMP_CAST (mp_limb_t, 0)) >> GMP_NAIL_BITS)
#define GMP_NUMB_MAX GMP_NUMB_MASK
#define GMP_NAIL_MASK (~ GMP_NUMB_MASK)






#define __GNU_MP__ 5

#define __need_size_t 



# 1 "/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.2/include/stddef.h" 1 3 4
# 187 "/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.2/include/stddef.h" 3 4
#define __size_t__ 
#define __SIZE_T__ 
#define _SIZE_T 
#define _SYS_SIZE_T_H 
#define _T_SIZE_ 
#define _T_SIZE 
#define __SIZE_T 
#define _SIZE_T_ 
#define _BSD_SIZE_T_ 
#define _SIZE_T_DEFINED_ 
#define _SIZE_T_DEFINED 
#define _BSD_SIZE_T_DEFINED_ 
#define _SIZE_T_DECLARED 
#define ___int_size_t_h 
#define _GCC_SIZE_T 
#define _SIZET_ 




#define __size_t 





typedef long unsigned int size_t;
# 235 "/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.2/include/stddef.h" 3 4
#undef __need_size_t
# 409 "/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.2/include/stddef.h" 3 4
#undef __need_NULL
# 54 "../gmp.h" 2

#undef __need_size_t




#define __GMP_LIBGMP_DLL 0
# 102 "../gmp.h"
#define __GMP_DECLSPEC_EXPORT __declspec(__dllexport__)
#define __GMP_DECLSPEC_IMPORT __declspec(__dllimport__)
# 128 "../gmp.h"
#define __GMP_DECLSPEC 
# 140 "../gmp.h"
typedef unsigned long int mp_limb_t;
typedef long int mp_limb_signed_t;


typedef unsigned long int mp_bitcnt_t;




typedef struct
{
  int _mp_alloc;

  int _mp_size;


  mp_limb_t *_mp_d;
} __mpz_struct;




typedef __mpz_struct MP_INT;
typedef __mpz_struct mpz_t[1];

typedef mp_limb_t * mp_ptr;
typedef const mp_limb_t * mp_srcptr;






#define __GMP_MP_SIZE_T_INT 0
typedef long int mp_size_t;
typedef long int mp_exp_t;


typedef struct
{
  __mpz_struct _mp_num;
  __mpz_struct _mp_den;
} __mpq_struct;

typedef __mpq_struct MP_RAT;
typedef __mpq_struct mpq_t[1];

typedef struct
{
  int _mp_prec;



  int _mp_size;


  mp_exp_t _mp_exp;
  mp_limb_t *_mp_d;
} __mpf_struct;


typedef __mpf_struct mpf_t[1];


typedef enum
{
  GMP_RAND_ALG_DEFAULT = 0,
  GMP_RAND_ALG_LC = GMP_RAND_ALG_DEFAULT
} gmp_randalg_t;


typedef struct
{
  mpz_t _mp_seed;
  gmp_randalg_t _mp_alg;
  union {
    void *_mp_lc;
  } _mp_algdata;
} __gmp_randstate_struct;
typedef __gmp_randstate_struct gmp_randstate_t[1];



typedef const __mpz_struct *mpz_srcptr;
typedef __mpz_struct *mpz_ptr;
typedef const __mpf_struct *mpf_srcptr;
typedef __mpf_struct *mpf_ptr;
typedef const __mpq_struct *mpq_srcptr;
typedef __mpq_struct *mpq_ptr;
# 243 "../gmp.h"
#define __GMP_DECLSPEC_XX 




#define __MPN(x) __gmpn_ ##x
# 296 "../gmp.h"
#define __GMP_GNUC_PREREQ(maj,min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
# 308 "../gmp.h"
#define __GMP_ATTRIBUTE_PURE __attribute__ ((__pure__))
# 324 "../gmp.h"
#define __GMP_CAST(type,expr) ((type) (expr))
# 348 "../gmp.h"
#define __GMP_NOTHROW 
# 364 "../gmp.h"
#define __GMP_EXTERN_INLINE extern __inline__ __attribute__ ((__gnu_inline__))



#define __GMP_INLINE_PROTOTYPES 1
# 444 "../gmp.h"
#define __GMP_ABS(x) ((x) >= 0 ? (x) : -(x))
#define __GMP_MAX(h,i) ((h) > (i) ? (h) : (i))



#define __GMP_UINT_MAX (~ (unsigned) 0)
#define __GMP_ULONG_MAX (~ (unsigned long) 0)
#define __GMP_USHRT_MAX ((unsigned short) ~0)




#define __GMP_LIKELY(cond) __builtin_expect ((cond) != 0, 1)
#define __GMP_UNLIKELY(cond) __builtin_expect ((cond) != 0, 0)
# 466 "../gmp.h"
#define __GMP_CRAY_Pragma(str) 




#define mpq_numref(Q) (&((Q)->_mp_num))
#define mpq_denref(Q) (&((Q)->_mp_den))







#define mp_set_memory_functions __gmp_set_memory_functions
 void __gmp_set_memory_functions (void *(*) (size_t),
          void *(*) (void *, size_t, size_t),
          void (*) (void *, size_t)) ;

#define mp_get_memory_functions __gmp_get_memory_functions
 void __gmp_get_memory_functions (void *(**) (size_t),
                                      void *(**) (void *, size_t, size_t),
                                      void (**) (void *, size_t)) ;

#define mp_bits_per_limb __gmp_bits_per_limb
 extern const int __gmp_bits_per_limb;

#define gmp_errno __gmp_errno
 extern int __gmp_errno;

#define gmp_version __gmp_version
 extern const char * const __gmp_version;





#define gmp_randinit __gmp_randinit
 void __gmp_randinit (gmp_randstate_t, gmp_randalg_t, ...);

#define gmp_randinit_default __gmp_randinit_default
 void __gmp_randinit_default (gmp_randstate_t);

#define gmp_randinit_lc_2exp __gmp_randinit_lc_2exp
 void __gmp_randinit_lc_2exp (gmp_randstate_t, mpz_srcptr, unsigned long int, mp_bitcnt_t);

#define gmp_randinit_lc_2exp_size __gmp_randinit_lc_2exp_size
 int __gmp_randinit_lc_2exp_size (gmp_randstate_t, mp_bitcnt_t);

#define gmp_randinit_mt __gmp_randinit_mt
 void __gmp_randinit_mt (gmp_randstate_t);

#define gmp_randinit_set __gmp_randinit_set
 void __gmp_randinit_set (gmp_randstate_t, const __gmp_randstate_struct *);

#define gmp_randseed __gmp_randseed
 void __gmp_randseed (gmp_randstate_t, mpz_srcptr);

#define gmp_randseed_ui __gmp_randseed_ui
 void __gmp_randseed_ui (gmp_randstate_t, unsigned long int);

#define gmp_randclear __gmp_randclear
 void __gmp_randclear (gmp_randstate_t);

#define gmp_urandomb_ui __gmp_urandomb_ui
 unsigned long __gmp_urandomb_ui (gmp_randstate_t, unsigned long);

#define gmp_urandomm_ui __gmp_urandomm_ui
 unsigned long __gmp_urandomm_ui (gmp_randstate_t, unsigned long);




#define gmp_asprintf __gmp_asprintf
 int __gmp_asprintf (char **, const char *, ...);

#define gmp_fprintf __gmp_fprintf




#define gmp_obstack_printf __gmp_obstack_printf




#define gmp_obstack_vprintf __gmp_obstack_vprintf




#define gmp_printf __gmp_printf
 int __gmp_printf (const char *, ...);

#define gmp_snprintf __gmp_snprintf
 int __gmp_snprintf (char *, size_t, const char *, ...);

#define gmp_sprintf __gmp_sprintf
 int __gmp_sprintf (char *, const char *, ...);

#define gmp_vasprintf __gmp_vasprintf




#define gmp_vfprintf __gmp_vfprintf




#define gmp_vprintf __gmp_vprintf




#define gmp_vsnprintf __gmp_vsnprintf




#define gmp_vsprintf __gmp_vsprintf







#define gmp_fscanf __gmp_fscanf




#define gmp_scanf __gmp_scanf
 int __gmp_scanf (const char *, ...);

#define gmp_sscanf __gmp_sscanf
 int __gmp_sscanf (const char *, const char *, ...);

#define gmp_vfscanf __gmp_vfscanf




#define gmp_vscanf __gmp_vscanf




#define gmp_vsscanf __gmp_vsscanf







#define _mpz_realloc __gmpz_realloc
#define mpz_realloc __gmpz_realloc
 void *__gmpz_realloc (mpz_ptr, mp_size_t);

#define mpz_abs __gmpz_abs

 void __gmpz_abs (mpz_ptr, mpz_srcptr);


#define mpz_add __gmpz_add
 void __gmpz_add (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_add_ui __gmpz_add_ui
 void __gmpz_add_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_addmul __gmpz_addmul
 void __gmpz_addmul (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_addmul_ui __gmpz_addmul_ui
 void __gmpz_addmul_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_and __gmpz_and
 void __gmpz_and (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_array_init __gmpz_array_init
 void __gmpz_array_init (mpz_ptr, mp_size_t, mp_size_t);

#define mpz_bin_ui __gmpz_bin_ui
 void __gmpz_bin_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_bin_uiui __gmpz_bin_uiui
 void __gmpz_bin_uiui (mpz_ptr, unsigned long int, unsigned long int);

#define mpz_cdiv_q __gmpz_cdiv_q
 void __gmpz_cdiv_q (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_cdiv_q_2exp __gmpz_cdiv_q_2exp
 void __gmpz_cdiv_q_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_cdiv_q_ui __gmpz_cdiv_q_ui
 unsigned long int __gmpz_cdiv_q_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_cdiv_qr __gmpz_cdiv_qr
 void __gmpz_cdiv_qr (mpz_ptr, mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_cdiv_qr_ui __gmpz_cdiv_qr_ui
 unsigned long int __gmpz_cdiv_qr_ui (mpz_ptr, mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_cdiv_r __gmpz_cdiv_r
 void __gmpz_cdiv_r (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_cdiv_r_2exp __gmpz_cdiv_r_2exp
 void __gmpz_cdiv_r_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_cdiv_r_ui __gmpz_cdiv_r_ui
 unsigned long int __gmpz_cdiv_r_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_cdiv_ui __gmpz_cdiv_ui
 unsigned long int __gmpz_cdiv_ui (mpz_srcptr, unsigned long int) __attribute__ ((__pure__));

#define mpz_clear __gmpz_clear
 void __gmpz_clear (mpz_ptr);

#define mpz_clears __gmpz_clears
 void __gmpz_clears (mpz_ptr, ...);

#define mpz_clrbit __gmpz_clrbit
 void __gmpz_clrbit (mpz_ptr, mp_bitcnt_t);

#define mpz_cmp __gmpz_cmp
 int __gmpz_cmp (mpz_srcptr, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_cmp_d __gmpz_cmp_d
 int __gmpz_cmp_d (mpz_srcptr, double) __attribute__ ((__pure__));

#define _mpz_cmp_si __gmpz_cmp_si
 int __gmpz_cmp_si (mpz_srcptr, signed long int) __attribute__ ((__pure__));

#define _mpz_cmp_ui __gmpz_cmp_ui
 int __gmpz_cmp_ui (mpz_srcptr, unsigned long int) __attribute__ ((__pure__));

#define mpz_cmpabs __gmpz_cmpabs
 int __gmpz_cmpabs (mpz_srcptr, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_cmpabs_d __gmpz_cmpabs_d
 int __gmpz_cmpabs_d (mpz_srcptr, double) __attribute__ ((__pure__));

#define mpz_cmpabs_ui __gmpz_cmpabs_ui
 int __gmpz_cmpabs_ui (mpz_srcptr, unsigned long int) __attribute__ ((__pure__));

#define mpz_com __gmpz_com
 void __gmpz_com (mpz_ptr, mpz_srcptr);

#define mpz_combit __gmpz_combit
 void __gmpz_combit (mpz_ptr, mp_bitcnt_t);

#define mpz_congruent_p __gmpz_congruent_p
 int __gmpz_congruent_p (mpz_srcptr, mpz_srcptr, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_congruent_2exp_p __gmpz_congruent_2exp_p
 int __gmpz_congruent_2exp_p (mpz_srcptr, mpz_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpz_congruent_ui_p __gmpz_congruent_ui_p
 int __gmpz_congruent_ui_p (mpz_srcptr, unsigned long, unsigned long) __attribute__ ((__pure__));

#define mpz_divexact __gmpz_divexact
 void __gmpz_divexact (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_divexact_ui __gmpz_divexact_ui
 void __gmpz_divexact_ui (mpz_ptr, mpz_srcptr, unsigned long);

#define mpz_divisible_p __gmpz_divisible_p
 int __gmpz_divisible_p (mpz_srcptr, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_divisible_ui_p __gmpz_divisible_ui_p
 int __gmpz_divisible_ui_p (mpz_srcptr, unsigned long) __attribute__ ((__pure__));

#define mpz_divisible_2exp_p __gmpz_divisible_2exp_p
 int __gmpz_divisible_2exp_p (mpz_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpz_dump __gmpz_dump
 void __gmpz_dump (mpz_srcptr);

#define mpz_export __gmpz_export
 void *__gmpz_export (void *, size_t *, int, size_t, int, size_t, mpz_srcptr);

#define mpz_fac_ui __gmpz_fac_ui
 void __gmpz_fac_ui (mpz_ptr, unsigned long int);

#define mpz_2fac_ui __gmpz_2fac_ui
 void __gmpz_2fac_ui (mpz_ptr, unsigned long int);

#define mpz_mfac_uiui __gmpz_mfac_uiui
 void __gmpz_mfac_uiui (mpz_ptr, unsigned long int, unsigned long int);

#define mpz_primorial_ui __gmpz_primorial_ui
 void __gmpz_primorial_ui (mpz_ptr, unsigned long int);

#define mpz_fdiv_q __gmpz_fdiv_q
 void __gmpz_fdiv_q (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_fdiv_q_2exp __gmpz_fdiv_q_2exp
 void __gmpz_fdiv_q_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_fdiv_q_ui __gmpz_fdiv_q_ui
 unsigned long int __gmpz_fdiv_q_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_fdiv_qr __gmpz_fdiv_qr
 void __gmpz_fdiv_qr (mpz_ptr, mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_fdiv_qr_ui __gmpz_fdiv_qr_ui
 unsigned long int __gmpz_fdiv_qr_ui (mpz_ptr, mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_fdiv_r __gmpz_fdiv_r
 void __gmpz_fdiv_r (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_fdiv_r_2exp __gmpz_fdiv_r_2exp
 void __gmpz_fdiv_r_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_fdiv_r_ui __gmpz_fdiv_r_ui
 unsigned long int __gmpz_fdiv_r_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_fdiv_ui __gmpz_fdiv_ui
 unsigned long int __gmpz_fdiv_ui (mpz_srcptr, unsigned long int) __attribute__ ((__pure__));

#define mpz_fib_ui __gmpz_fib_ui
 void __gmpz_fib_ui (mpz_ptr, unsigned long int);

#define mpz_fib2_ui __gmpz_fib2_ui
 void __gmpz_fib2_ui (mpz_ptr, mpz_ptr, unsigned long int);

#define mpz_fits_sint_p __gmpz_fits_sint_p
 int __gmpz_fits_sint_p (mpz_srcptr) __attribute__ ((__pure__));

#define mpz_fits_slong_p __gmpz_fits_slong_p
 int __gmpz_fits_slong_p (mpz_srcptr) __attribute__ ((__pure__));

#define mpz_fits_sshort_p __gmpz_fits_sshort_p
 int __gmpz_fits_sshort_p (mpz_srcptr) __attribute__ ((__pure__));

#define mpz_fits_uint_p __gmpz_fits_uint_p

 int __gmpz_fits_uint_p (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_fits_ulong_p __gmpz_fits_ulong_p

 int __gmpz_fits_ulong_p (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_fits_ushort_p __gmpz_fits_ushort_p

 int __gmpz_fits_ushort_p (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_gcd __gmpz_gcd
 void __gmpz_gcd (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_gcd_ui __gmpz_gcd_ui
 unsigned long int __gmpz_gcd_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_gcdext __gmpz_gcdext
 void __gmpz_gcdext (mpz_ptr, mpz_ptr, mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_get_d __gmpz_get_d
 double __gmpz_get_d (mpz_srcptr) __attribute__ ((__pure__));

#define mpz_get_d_2exp __gmpz_get_d_2exp
 double __gmpz_get_d_2exp (signed long int *, mpz_srcptr);

#define mpz_get_si __gmpz_get_si
 long int __gmpz_get_si (mpz_srcptr) __attribute__ ((__pure__));

#define mpz_get_str __gmpz_get_str
 char *__gmpz_get_str (char *, int, mpz_srcptr);

#define mpz_get_ui __gmpz_get_ui

 unsigned long int __gmpz_get_ui (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_getlimbn __gmpz_getlimbn

 mp_limb_t __gmpz_getlimbn (mpz_srcptr, mp_size_t) __attribute__ ((__pure__));


#define mpz_hamdist __gmpz_hamdist
 mp_bitcnt_t __gmpz_hamdist (mpz_srcptr, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_import __gmpz_import
 void __gmpz_import (mpz_ptr, size_t, int, size_t, int, size_t, const void *);

#define mpz_init __gmpz_init
 void __gmpz_init (mpz_ptr);

#define mpz_init2 __gmpz_init2
 void __gmpz_init2 (mpz_ptr, mp_bitcnt_t);

#define mpz_inits __gmpz_inits
 void __gmpz_inits (mpz_ptr, ...);

#define mpz_init_set __gmpz_init_set
 void __gmpz_init_set (mpz_ptr, mpz_srcptr);

#define mpz_init_set_d __gmpz_init_set_d
 void __gmpz_init_set_d (mpz_ptr, double);

#define mpz_init_set_si __gmpz_init_set_si
 void __gmpz_init_set_si (mpz_ptr, signed long int);

#define mpz_init_set_str __gmpz_init_set_str
 int __gmpz_init_set_str (mpz_ptr, const char *, int);

#define mpz_init_set_ui __gmpz_init_set_ui
 void __gmpz_init_set_ui (mpz_ptr, unsigned long int);

#define mpz_inp_raw __gmpz_inp_raw




#define mpz_inp_str __gmpz_inp_str




#define mpz_invert __gmpz_invert
 int __gmpz_invert (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_ior __gmpz_ior
 void __gmpz_ior (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_jacobi __gmpz_jacobi
 int __gmpz_jacobi (mpz_srcptr, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_kronecker mpz_jacobi

#define mpz_kronecker_si __gmpz_kronecker_si
 int __gmpz_kronecker_si (mpz_srcptr, long) __attribute__ ((__pure__));

#define mpz_kronecker_ui __gmpz_kronecker_ui
 int __gmpz_kronecker_ui (mpz_srcptr, unsigned long) __attribute__ ((__pure__));

#define mpz_si_kronecker __gmpz_si_kronecker
 int __gmpz_si_kronecker (long, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_ui_kronecker __gmpz_ui_kronecker
 int __gmpz_ui_kronecker (unsigned long, mpz_srcptr) __attribute__ ((__pure__));

#define mpz_lcm __gmpz_lcm
 void __gmpz_lcm (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_lcm_ui __gmpz_lcm_ui
 void __gmpz_lcm_ui (mpz_ptr, mpz_srcptr, unsigned long);

#define mpz_legendre mpz_jacobi

#define mpz_lucnum_ui __gmpz_lucnum_ui
 void __gmpz_lucnum_ui (mpz_ptr, unsigned long int);

#define mpz_lucnum2_ui __gmpz_lucnum2_ui
 void __gmpz_lucnum2_ui (mpz_ptr, mpz_ptr, unsigned long int);

#define mpz_millerrabin __gmpz_millerrabin
 int __gmpz_millerrabin (mpz_srcptr, int) __attribute__ ((__pure__));

#define mpz_mod __gmpz_mod
 void __gmpz_mod (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_mod_ui mpz_fdiv_r_ui

#define mpz_mul __gmpz_mul
 void __gmpz_mul (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_mul_2exp __gmpz_mul_2exp
 void __gmpz_mul_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_mul_si __gmpz_mul_si
 void __gmpz_mul_si (mpz_ptr, mpz_srcptr, long int);

#define mpz_mul_ui __gmpz_mul_ui
 void __gmpz_mul_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_neg __gmpz_neg

 void __gmpz_neg (mpz_ptr, mpz_srcptr);


#define mpz_nextprime __gmpz_nextprime
 void __gmpz_nextprime (mpz_ptr, mpz_srcptr);

#define mpz_out_raw __gmpz_out_raw




#define mpz_out_str __gmpz_out_str




#define mpz_perfect_power_p __gmpz_perfect_power_p
 int __gmpz_perfect_power_p (mpz_srcptr) __attribute__ ((__pure__));

#define mpz_perfect_square_p __gmpz_perfect_square_p

 int __gmpz_perfect_square_p (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_popcount __gmpz_popcount

 mp_bitcnt_t __gmpz_popcount (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_pow_ui __gmpz_pow_ui
 void __gmpz_pow_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_powm __gmpz_powm
 void __gmpz_powm (mpz_ptr, mpz_srcptr, mpz_srcptr, mpz_srcptr);

#define mpz_powm_sec __gmpz_powm_sec
 void __gmpz_powm_sec (mpz_ptr, mpz_srcptr, mpz_srcptr, mpz_srcptr);

#define mpz_powm_ui __gmpz_powm_ui
 void __gmpz_powm_ui (mpz_ptr, mpz_srcptr, unsigned long int, mpz_srcptr);

#define mpz_probab_prime_p __gmpz_probab_prime_p
 int __gmpz_probab_prime_p (mpz_srcptr, int) __attribute__ ((__pure__));

#define mpz_random __gmpz_random
 void __gmpz_random (mpz_ptr, mp_size_t);

#define mpz_random2 __gmpz_random2
 void __gmpz_random2 (mpz_ptr, mp_size_t);

#define mpz_realloc2 __gmpz_realloc2
 void __gmpz_realloc2 (mpz_ptr, mp_bitcnt_t);

#define mpz_remove __gmpz_remove
 mp_bitcnt_t __gmpz_remove (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_root __gmpz_root
 int __gmpz_root (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_rootrem __gmpz_rootrem
 void __gmpz_rootrem (mpz_ptr, mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_rrandomb __gmpz_rrandomb
 void __gmpz_rrandomb (mpz_ptr, gmp_randstate_t, mp_bitcnt_t);

#define mpz_scan0 __gmpz_scan0
 mp_bitcnt_t __gmpz_scan0 (mpz_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpz_scan1 __gmpz_scan1
 mp_bitcnt_t __gmpz_scan1 (mpz_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpz_set __gmpz_set
 void __gmpz_set (mpz_ptr, mpz_srcptr);

#define mpz_set_d __gmpz_set_d
 void __gmpz_set_d (mpz_ptr, double);

#define mpz_set_f __gmpz_set_f
 void __gmpz_set_f (mpz_ptr, mpf_srcptr);

#define mpz_set_q __gmpz_set_q

 void __gmpz_set_q (mpz_ptr, mpq_srcptr);


#define mpz_set_si __gmpz_set_si
 void __gmpz_set_si (mpz_ptr, signed long int);

#define mpz_set_str __gmpz_set_str
 int __gmpz_set_str (mpz_ptr, const char *, int);

#define mpz_set_ui __gmpz_set_ui
 void __gmpz_set_ui (mpz_ptr, unsigned long int);

#define mpz_setbit __gmpz_setbit
 void __gmpz_setbit (mpz_ptr, mp_bitcnt_t);

#define mpz_size __gmpz_size

 size_t __gmpz_size (mpz_srcptr) __attribute__ ((__pure__));


#define mpz_sizeinbase __gmpz_sizeinbase
 size_t __gmpz_sizeinbase (mpz_srcptr, int) __attribute__ ((__pure__));

#define mpz_sqrt __gmpz_sqrt
 void __gmpz_sqrt (mpz_ptr, mpz_srcptr);

#define mpz_sqrtrem __gmpz_sqrtrem
 void __gmpz_sqrtrem (mpz_ptr, mpz_ptr, mpz_srcptr);

#define mpz_sub __gmpz_sub
 void __gmpz_sub (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_sub_ui __gmpz_sub_ui
 void __gmpz_sub_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_ui_sub __gmpz_ui_sub
 void __gmpz_ui_sub (mpz_ptr, unsigned long int, mpz_srcptr);

#define mpz_submul __gmpz_submul
 void __gmpz_submul (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_submul_ui __gmpz_submul_ui
 void __gmpz_submul_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_swap __gmpz_swap
 void __gmpz_swap (mpz_ptr, mpz_ptr) ;

#define mpz_tdiv_ui __gmpz_tdiv_ui
 unsigned long int __gmpz_tdiv_ui (mpz_srcptr, unsigned long int) __attribute__ ((__pure__));

#define mpz_tdiv_q __gmpz_tdiv_q
 void __gmpz_tdiv_q (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_tdiv_q_2exp __gmpz_tdiv_q_2exp
 void __gmpz_tdiv_q_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_tdiv_q_ui __gmpz_tdiv_q_ui
 unsigned long int __gmpz_tdiv_q_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_tdiv_qr __gmpz_tdiv_qr
 void __gmpz_tdiv_qr (mpz_ptr, mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_tdiv_qr_ui __gmpz_tdiv_qr_ui
 unsigned long int __gmpz_tdiv_qr_ui (mpz_ptr, mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_tdiv_r __gmpz_tdiv_r
 void __gmpz_tdiv_r (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_tdiv_r_2exp __gmpz_tdiv_r_2exp
 void __gmpz_tdiv_r_2exp (mpz_ptr, mpz_srcptr, mp_bitcnt_t);

#define mpz_tdiv_r_ui __gmpz_tdiv_r_ui
 unsigned long int __gmpz_tdiv_r_ui (mpz_ptr, mpz_srcptr, unsigned long int);

#define mpz_tstbit __gmpz_tstbit
 int __gmpz_tstbit (mpz_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpz_ui_pow_ui __gmpz_ui_pow_ui
 void __gmpz_ui_pow_ui (mpz_ptr, unsigned long int, unsigned long int);

#define mpz_urandomb __gmpz_urandomb
 void __gmpz_urandomb (mpz_ptr, gmp_randstate_t, mp_bitcnt_t);

#define mpz_urandomm __gmpz_urandomm
 void __gmpz_urandomm (mpz_ptr, gmp_randstate_t, mpz_srcptr);

#define mpz_xor __gmpz_xor
#define mpz_eor __gmpz_xor
 void __gmpz_xor (mpz_ptr, mpz_srcptr, mpz_srcptr);




#define mpq_abs __gmpq_abs

 void __gmpq_abs (mpq_ptr, mpq_srcptr);


#define mpq_add __gmpq_add
 void __gmpq_add (mpq_ptr, mpq_srcptr, mpq_srcptr);

#define mpq_canonicalize __gmpq_canonicalize
 void __gmpq_canonicalize (mpq_ptr);

#define mpq_clear __gmpq_clear
 void __gmpq_clear (mpq_ptr);

#define mpq_clears __gmpq_clears
 void __gmpq_clears (mpq_ptr, ...);

#define mpq_cmp __gmpq_cmp
 int __gmpq_cmp (mpq_srcptr, mpq_srcptr) __attribute__ ((__pure__));

#define _mpq_cmp_si __gmpq_cmp_si
 int __gmpq_cmp_si (mpq_srcptr, long, unsigned long) __attribute__ ((__pure__));

#define _mpq_cmp_ui __gmpq_cmp_ui
 int __gmpq_cmp_ui (mpq_srcptr, unsigned long int, unsigned long int) __attribute__ ((__pure__));

#define mpq_div __gmpq_div
 void __gmpq_div (mpq_ptr, mpq_srcptr, mpq_srcptr);

#define mpq_div_2exp __gmpq_div_2exp
 void __gmpq_div_2exp (mpq_ptr, mpq_srcptr, mp_bitcnt_t);

#define mpq_equal __gmpq_equal
 int __gmpq_equal (mpq_srcptr, mpq_srcptr) __attribute__ ((__pure__));

#define mpq_get_num __gmpq_get_num
 void __gmpq_get_num (mpz_ptr, mpq_srcptr);

#define mpq_get_den __gmpq_get_den
 void __gmpq_get_den (mpz_ptr, mpq_srcptr);

#define mpq_get_d __gmpq_get_d
 double __gmpq_get_d (mpq_srcptr) __attribute__ ((__pure__));

#define mpq_get_str __gmpq_get_str
 char *__gmpq_get_str (char *, int, mpq_srcptr);

#define mpq_init __gmpq_init
 void __gmpq_init (mpq_ptr);

#define mpq_inits __gmpq_inits
 void __gmpq_inits (mpq_ptr, ...);

#define mpq_inp_str __gmpq_inp_str




#define mpq_inv __gmpq_inv
 void __gmpq_inv (mpq_ptr, mpq_srcptr);

#define mpq_mul __gmpq_mul
 void __gmpq_mul (mpq_ptr, mpq_srcptr, mpq_srcptr);

#define mpq_mul_2exp __gmpq_mul_2exp
 void __gmpq_mul_2exp (mpq_ptr, mpq_srcptr, mp_bitcnt_t);

#define mpq_neg __gmpq_neg

 void __gmpq_neg (mpq_ptr, mpq_srcptr);


#define mpq_out_str __gmpq_out_str




#define mpq_set __gmpq_set
 void __gmpq_set (mpq_ptr, mpq_srcptr);

#define mpq_set_d __gmpq_set_d
 void __gmpq_set_d (mpq_ptr, double);

#define mpq_set_den __gmpq_set_den
 void __gmpq_set_den (mpq_ptr, mpz_srcptr);

#define mpq_set_f __gmpq_set_f
 void __gmpq_set_f (mpq_ptr, mpf_srcptr);

#define mpq_set_num __gmpq_set_num
 void __gmpq_set_num (mpq_ptr, mpz_srcptr);

#define mpq_set_si __gmpq_set_si
 void __gmpq_set_si (mpq_ptr, signed long int, unsigned long int);

#define mpq_set_str __gmpq_set_str
 int __gmpq_set_str (mpq_ptr, const char *, int);

#define mpq_set_ui __gmpq_set_ui
 void __gmpq_set_ui (mpq_ptr, unsigned long int, unsigned long int);

#define mpq_set_z __gmpq_set_z
 void __gmpq_set_z (mpq_ptr, mpz_srcptr);

#define mpq_sub __gmpq_sub
 void __gmpq_sub (mpq_ptr, mpq_srcptr, mpq_srcptr);

#define mpq_swap __gmpq_swap
 void __gmpq_swap (mpq_ptr, mpq_ptr) ;




#define mpf_abs __gmpf_abs
 void __gmpf_abs (mpf_ptr, mpf_srcptr);

#define mpf_add __gmpf_add
 void __gmpf_add (mpf_ptr, mpf_srcptr, mpf_srcptr);

#define mpf_add_ui __gmpf_add_ui
 void __gmpf_add_ui (mpf_ptr, mpf_srcptr, unsigned long int);
#define mpf_ceil __gmpf_ceil
 void __gmpf_ceil (mpf_ptr, mpf_srcptr);

#define mpf_clear __gmpf_clear
 void __gmpf_clear (mpf_ptr);

#define mpf_clears __gmpf_clears
 void __gmpf_clears (mpf_ptr, ...);

#define mpf_cmp __gmpf_cmp
 int __gmpf_cmp (mpf_srcptr, mpf_srcptr) __attribute__ ((__pure__));

#define mpf_cmp_d __gmpf_cmp_d
 int __gmpf_cmp_d (mpf_srcptr, double) __attribute__ ((__pure__));

#define mpf_cmp_si __gmpf_cmp_si
 int __gmpf_cmp_si (mpf_srcptr, signed long int) __attribute__ ((__pure__));

#define mpf_cmp_ui __gmpf_cmp_ui
 int __gmpf_cmp_ui (mpf_srcptr, unsigned long int) __attribute__ ((__pure__));

#define mpf_div __gmpf_div
 void __gmpf_div (mpf_ptr, mpf_srcptr, mpf_srcptr);

#define mpf_div_2exp __gmpf_div_2exp
 void __gmpf_div_2exp (mpf_ptr, mpf_srcptr, mp_bitcnt_t);

#define mpf_div_ui __gmpf_div_ui
 void __gmpf_div_ui (mpf_ptr, mpf_srcptr, unsigned long int);

#define mpf_dump __gmpf_dump
 void __gmpf_dump (mpf_srcptr);

#define mpf_eq __gmpf_eq
 int __gmpf_eq (mpf_srcptr, mpf_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpf_fits_sint_p __gmpf_fits_sint_p
 int __gmpf_fits_sint_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_fits_slong_p __gmpf_fits_slong_p
 int __gmpf_fits_slong_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_fits_sshort_p __gmpf_fits_sshort_p
 int __gmpf_fits_sshort_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_fits_uint_p __gmpf_fits_uint_p
 int __gmpf_fits_uint_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_fits_ulong_p __gmpf_fits_ulong_p
 int __gmpf_fits_ulong_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_fits_ushort_p __gmpf_fits_ushort_p
 int __gmpf_fits_ushort_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_floor __gmpf_floor
 void __gmpf_floor (mpf_ptr, mpf_srcptr);

#define mpf_get_d __gmpf_get_d
 double __gmpf_get_d (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_get_d_2exp __gmpf_get_d_2exp
 double __gmpf_get_d_2exp (signed long int *, mpf_srcptr);

#define mpf_get_default_prec __gmpf_get_default_prec
 mp_bitcnt_t __gmpf_get_default_prec (void) __attribute__ ((__pure__));

#define mpf_get_prec __gmpf_get_prec
 mp_bitcnt_t __gmpf_get_prec (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_get_si __gmpf_get_si
 long __gmpf_get_si (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_get_str __gmpf_get_str
 char *__gmpf_get_str (char *, mp_exp_t *, int, size_t, mpf_srcptr);

#define mpf_get_ui __gmpf_get_ui
 unsigned long __gmpf_get_ui (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_init __gmpf_init
 void __gmpf_init (mpf_ptr);

#define mpf_init2 __gmpf_init2
 void __gmpf_init2 (mpf_ptr, mp_bitcnt_t);

#define mpf_inits __gmpf_inits
 void __gmpf_inits (mpf_ptr, ...);

#define mpf_init_set __gmpf_init_set
 void __gmpf_init_set (mpf_ptr, mpf_srcptr);

#define mpf_init_set_d __gmpf_init_set_d
 void __gmpf_init_set_d (mpf_ptr, double);

#define mpf_init_set_si __gmpf_init_set_si
 void __gmpf_init_set_si (mpf_ptr, signed long int);

#define mpf_init_set_str __gmpf_init_set_str
 int __gmpf_init_set_str (mpf_ptr, const char *, int);

#define mpf_init_set_ui __gmpf_init_set_ui
 void __gmpf_init_set_ui (mpf_ptr, unsigned long int);

#define mpf_inp_str __gmpf_inp_str




#define mpf_integer_p __gmpf_integer_p
 int __gmpf_integer_p (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_mul __gmpf_mul
 void __gmpf_mul (mpf_ptr, mpf_srcptr, mpf_srcptr);

#define mpf_mul_2exp __gmpf_mul_2exp
 void __gmpf_mul_2exp (mpf_ptr, mpf_srcptr, mp_bitcnt_t);

#define mpf_mul_ui __gmpf_mul_ui
 void __gmpf_mul_ui (mpf_ptr, mpf_srcptr, unsigned long int);

#define mpf_neg __gmpf_neg
 void __gmpf_neg (mpf_ptr, mpf_srcptr);

#define mpf_out_str __gmpf_out_str




#define mpf_pow_ui __gmpf_pow_ui
 void __gmpf_pow_ui (mpf_ptr, mpf_srcptr, unsigned long int);

#define mpf_random2 __gmpf_random2
 void __gmpf_random2 (mpf_ptr, mp_size_t, mp_exp_t);

#define mpf_reldiff __gmpf_reldiff
 void __gmpf_reldiff (mpf_ptr, mpf_srcptr, mpf_srcptr);

#define mpf_set __gmpf_set
 void __gmpf_set (mpf_ptr, mpf_srcptr);

#define mpf_set_d __gmpf_set_d
 void __gmpf_set_d (mpf_ptr, double);

#define mpf_set_default_prec __gmpf_set_default_prec
 void __gmpf_set_default_prec (mp_bitcnt_t) ;

#define mpf_set_prec __gmpf_set_prec
 void __gmpf_set_prec (mpf_ptr, mp_bitcnt_t);

#define mpf_set_prec_raw __gmpf_set_prec_raw
 void __gmpf_set_prec_raw (mpf_ptr, mp_bitcnt_t) ;

#define mpf_set_q __gmpf_set_q
 void __gmpf_set_q (mpf_ptr, mpq_srcptr);

#define mpf_set_si __gmpf_set_si
 void __gmpf_set_si (mpf_ptr, signed long int);

#define mpf_set_str __gmpf_set_str
 int __gmpf_set_str (mpf_ptr, const char *, int);

#define mpf_set_ui __gmpf_set_ui
 void __gmpf_set_ui (mpf_ptr, unsigned long int);

#define mpf_set_z __gmpf_set_z
 void __gmpf_set_z (mpf_ptr, mpz_srcptr);

#define mpf_size __gmpf_size
 size_t __gmpf_size (mpf_srcptr) __attribute__ ((__pure__));

#define mpf_sqrt __gmpf_sqrt
 void __gmpf_sqrt (mpf_ptr, mpf_srcptr);

#define mpf_sqrt_ui __gmpf_sqrt_ui
 void __gmpf_sqrt_ui (mpf_ptr, unsigned long int);

#define mpf_sub __gmpf_sub
 void __gmpf_sub (mpf_ptr, mpf_srcptr, mpf_srcptr);

#define mpf_sub_ui __gmpf_sub_ui
 void __gmpf_sub_ui (mpf_ptr, mpf_srcptr, unsigned long int);

#define mpf_swap __gmpf_swap
 void __gmpf_swap (mpf_ptr, mpf_ptr) ;

#define mpf_trunc __gmpf_trunc
 void __gmpf_trunc (mpf_ptr, mpf_srcptr);

#define mpf_ui_div __gmpf_ui_div
 void __gmpf_ui_div (mpf_ptr, unsigned long int, mpf_srcptr);

#define mpf_ui_sub __gmpf_ui_sub
 void __gmpf_ui_sub (mpf_ptr, unsigned long int, mpf_srcptr);

#define mpf_urandomb __gmpf_urandomb
 void __gmpf_urandomb (mpf_t, gmp_randstate_t, mp_bitcnt_t);






#define mpn_add __MPN(add)

 mp_limb_t __gmpn_add (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);


#define mpn_add_1 __MPN(add_1)

 mp_limb_t __gmpn_add_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t) ;


#define mpn_add_n __MPN(add_n)
 mp_limb_t __gmpn_add_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_addmul_1 __MPN(addmul_1)
 mp_limb_t __gmpn_addmul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_cmp __MPN(cmp)

 int __gmpn_cmp (mp_srcptr, mp_srcptr, mp_size_t) __attribute__ ((__pure__));


#define mpn_divexact_by3(dst,src,size) mpn_divexact_by3c (dst, src, size, __GMP_CAST (mp_limb_t, 0))


#define mpn_divexact_by3c __MPN(divexact_by3c)
 mp_limb_t __gmpn_divexact_by3c (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_divmod_1(qp,np,nsize,dlimb) mpn_divrem_1 (qp, __GMP_CAST (mp_size_t, 0), np, nsize, dlimb)


#define mpn_divrem __MPN(divrem)
 mp_limb_t __gmpn_divrem (mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_divrem_1 __MPN(divrem_1)
 mp_limb_t __gmpn_divrem_1 (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_divrem_2 __MPN(divrem_2)
 mp_limb_t __gmpn_divrem_2 (mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_srcptr);

#define mpn_div_qr_2 __MPN(div_qr_2)
 mp_limb_t __gmpn_div_qr_2 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_gcd __MPN(gcd)
 mp_size_t __gmpn_gcd (mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_size_t);

#define mpn_gcd_1 __MPN(gcd_1)
 mp_limb_t __gmpn_gcd_1 (mp_srcptr, mp_size_t, mp_limb_t) __attribute__ ((__pure__));

#define mpn_gcdext_1 __MPN(gcdext_1)
 mp_limb_t __gmpn_gcdext_1 (mp_limb_signed_t *, mp_limb_signed_t *, mp_limb_t, mp_limb_t);

#define mpn_gcdext __MPN(gcdext)
 mp_size_t __gmpn_gcdext (mp_ptr, mp_ptr, mp_size_t *, mp_ptr, mp_size_t, mp_ptr, mp_size_t);

#define mpn_get_str __MPN(get_str)
 size_t __gmpn_get_str (unsigned char *, int, mp_ptr, mp_size_t);

#define mpn_hamdist __MPN(hamdist)
 mp_bitcnt_t __gmpn_hamdist (mp_srcptr, mp_srcptr, mp_size_t) __attribute__ ((__pure__));

#define mpn_lshift __MPN(lshift)
 mp_limb_t __gmpn_lshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int);

#define mpn_mod_1 __MPN(mod_1)
 mp_limb_t __gmpn_mod_1 (mp_srcptr, mp_size_t, mp_limb_t) __attribute__ ((__pure__));

#define mpn_mul __MPN(mul)
 mp_limb_t __gmpn_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_mul_1 __MPN(mul_1)
 mp_limb_t __gmpn_mul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_mul_n __MPN(mul_n)
 void __gmpn_mul_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_sqr __MPN(sqr)
 void __gmpn_sqr (mp_ptr, mp_srcptr, mp_size_t);

#define mpn_neg __MPN(neg)

 mp_limb_t __gmpn_neg (mp_ptr, mp_srcptr, mp_size_t);


#define mpn_com __MPN(com)

 void __gmpn_com (mp_ptr, mp_srcptr, mp_size_t);


#define mpn_perfect_square_p __MPN(perfect_square_p)
 int __gmpn_perfect_square_p (mp_srcptr, mp_size_t) __attribute__ ((__pure__));

#define mpn_perfect_power_p __MPN(perfect_power_p)
 int __gmpn_perfect_power_p (mp_srcptr, mp_size_t) __attribute__ ((__pure__));

#define mpn_popcount __MPN(popcount)
 mp_bitcnt_t __gmpn_popcount (mp_srcptr, mp_size_t) __attribute__ ((__pure__));

#define mpn_pow_1 __MPN(pow_1)
 mp_size_t __gmpn_pow_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);


#define mpn_preinv_mod_1 __MPN(preinv_mod_1)
 mp_limb_t __gmpn_preinv_mod_1 (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t) __attribute__ ((__pure__));

#define mpn_random __MPN(random)
 void __gmpn_random (mp_ptr, mp_size_t);

#define mpn_random2 __MPN(random2)
 void __gmpn_random2 (mp_ptr, mp_size_t);

#define mpn_rshift __MPN(rshift)
 mp_limb_t __gmpn_rshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int);

#define mpn_scan0 __MPN(scan0)
 mp_bitcnt_t __gmpn_scan0 (mp_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpn_scan1 __MPN(scan1)
 mp_bitcnt_t __gmpn_scan1 (mp_srcptr, mp_bitcnt_t) __attribute__ ((__pure__));

#define mpn_set_str __MPN(set_str)
 mp_size_t __gmpn_set_str (mp_ptr, const unsigned char *, size_t, int);

#define mpn_sqrtrem __MPN(sqrtrem)
 mp_size_t __gmpn_sqrtrem (mp_ptr, mp_ptr, mp_srcptr, mp_size_t);

#define mpn_sub __MPN(sub)

 mp_limb_t __gmpn_sub (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);


#define mpn_sub_1 __MPN(sub_1)

 mp_limb_t __gmpn_sub_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t) ;


#define mpn_sub_n __MPN(sub_n)
 mp_limb_t __gmpn_sub_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_submul_1 __MPN(submul_1)
 mp_limb_t __gmpn_submul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_tdiv_qr __MPN(tdiv_qr)
 void __gmpn_tdiv_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_and_n __MPN(and_n)
 void __gmpn_and_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_andn_n __MPN(andn_n)
 void __gmpn_andn_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_nand_n __MPN(nand_n)
 void __gmpn_nand_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_ior_n __MPN(ior_n)
 void __gmpn_ior_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_iorn_n __MPN(iorn_n)
 void __gmpn_iorn_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_nior_n __MPN(nior_n)
 void __gmpn_nior_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_xor_n __MPN(xor_n)
 void __gmpn_xor_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_xnor_n __MPN(xnor_n)
 void __gmpn_xnor_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_copyi __MPN(copyi)
 void __gmpn_copyi (mp_ptr, mp_srcptr, mp_size_t);
#define mpn_copyd __MPN(copyd)
 void __gmpn_copyd (mp_ptr, mp_srcptr, mp_size_t);
#define mpn_zero __MPN(zero)
 void __gmpn_zero (mp_ptr, mp_size_t);
# 1630 "../gmp.h"
extern __inline__ __attribute__ ((__gnu_inline__)) void
__gmpz_abs (mpz_ptr __gmp_w, mpz_srcptr __gmp_u)
{
  if (__gmp_w != __gmp_u)
    __gmpz_set (__gmp_w, __gmp_u);
  __gmp_w->_mp_size = ((__gmp_w->_mp_size) >= 0 ? (__gmp_w->_mp_size) : -(__gmp_w->_mp_size));
}



#define __GMPZ_FITS_UTYPE_P(z,maxval) mp_size_t __gmp_n = z->_mp_size; mp_ptr __gmp_p = z->_mp_d; return (__gmp_n == 0 || (__gmp_n == 1 && __gmp_p[0] <= maxval));
# 1654 "../gmp.h"
extern __inline__ __attribute__ ((__gnu_inline__))

int
__gmpz_fits_uint_p (mpz_srcptr __gmp_z)
{
  mp_size_t __gmp_n = __gmp_z->_mp_size; mp_ptr __gmp_p = __gmp_z->_mp_d; return (__gmp_n == 0 || (__gmp_n == 1 && __gmp_p[0] <= (~ (unsigned) 0)));;
}




extern __inline__ __attribute__ ((__gnu_inline__))

int
__gmpz_fits_ulong_p (mpz_srcptr __gmp_z)
{
  mp_size_t __gmp_n = __gmp_z->_mp_size; mp_ptr __gmp_p = __gmp_z->_mp_d; return (__gmp_n == 0 || (__gmp_n == 1 && __gmp_p[0] <= (~ (unsigned long) 0)));;
}




extern __inline__ __attribute__ ((__gnu_inline__))

int
__gmpz_fits_ushort_p (mpz_srcptr __gmp_z)
{
  mp_size_t __gmp_n = __gmp_z->_mp_size; mp_ptr __gmp_p = __gmp_z->_mp_d; return (__gmp_n == 0 || (__gmp_n == 1 && __gmp_p[0] <= ((unsigned short) ~0)));;
}




extern __inline__ __attribute__ ((__gnu_inline__))

unsigned long
__gmpz_get_ui (mpz_srcptr __gmp_z)
{
  mp_ptr __gmp_p = __gmp_z->_mp_d;
  mp_size_t __gmp_n = __gmp_z->_mp_size;
  mp_limb_t __gmp_l = __gmp_p[0];






  return (__gmp_n != 0 ? __gmp_l : 0);
# 1710 "../gmp.h"
}




extern __inline__ __attribute__ ((__gnu_inline__))

mp_limb_t
__gmpz_getlimbn (mpz_srcptr __gmp_z, mp_size_t __gmp_n)
{
  mp_limb_t __gmp_result = 0;
  if (__builtin_expect ((__gmp_n >= 0 && __gmp_n < ((__gmp_z->_mp_size) >= 0 ? (__gmp_z->_mp_size) : -(__gmp_z->_mp_size))) != 0, 1))
    __gmp_result = __gmp_z->_mp_d[__gmp_n];
  return __gmp_result;
}



extern __inline__ __attribute__ ((__gnu_inline__)) void
__gmpz_neg (mpz_ptr __gmp_w, mpz_srcptr __gmp_u)
{
  if (__gmp_w != __gmp_u)
    __gmpz_set (__gmp_w, __gmp_u);
  __gmp_w->_mp_size = - __gmp_w->_mp_size;
}




extern __inline__ __attribute__ ((__gnu_inline__))

int
__gmpz_perfect_square_p (mpz_srcptr __gmp_a)
{
  mp_size_t __gmp_asize;
  int __gmp_result;

  __gmp_asize = __gmp_a->_mp_size;
  __gmp_result = (__gmp_asize >= 0);
  if (__builtin_expect ((__gmp_asize > 0) != 0, 1))
    __gmp_result = __gmpn_perfect_square_p (__gmp_a->_mp_d, __gmp_asize);
  return __gmp_result;
}




extern __inline__ __attribute__ ((__gnu_inline__))

mp_bitcnt_t
__gmpz_popcount (mpz_srcptr __gmp_u)
{
  mp_size_t __gmp_usize;
  mp_bitcnt_t __gmp_result;

  __gmp_usize = __gmp_u->_mp_size;
  __gmp_result = (__gmp_usize < 0 ? (~ (unsigned long) 0) : 0);
  if (__builtin_expect ((__gmp_usize > 0) != 0, 1))
    __gmp_result = __gmpn_popcount (__gmp_u->_mp_d, __gmp_usize);
  return __gmp_result;
}




extern __inline__ __attribute__ ((__gnu_inline__))

void
__gmpz_set_q (mpz_ptr __gmp_w, mpq_srcptr __gmp_u)
{
  __gmpz_tdiv_q (__gmp_w, (&((__gmp_u)->_mp_num)), (&((__gmp_u)->_mp_den)));
}




extern __inline__ __attribute__ ((__gnu_inline__))

size_t
__gmpz_size (mpz_srcptr __gmp_z)
{
  return ((__gmp_z->_mp_size) >= 0 ? (__gmp_z->_mp_size) : -(__gmp_z->_mp_size));
}






extern __inline__ __attribute__ ((__gnu_inline__)) void
__gmpq_abs (mpq_ptr __gmp_w, mpq_srcptr __gmp_u)
{
  if (__gmp_w != __gmp_u)
    __gmpq_set (__gmp_w, __gmp_u);
  __gmp_w->_mp_num._mp_size = ((__gmp_w->_mp_num._mp_size) >= 0 ? (__gmp_w->_mp_num._mp_size) : -(__gmp_w->_mp_num._mp_size));
}



extern __inline__ __attribute__ ((__gnu_inline__)) void
__gmpq_neg (mpq_ptr __gmp_w, mpq_srcptr __gmp_u)
{
  if (__gmp_w != __gmp_u)
    __gmpq_set (__gmp_w, __gmp_u);
  __gmp_w->_mp_num._mp_size = - __gmp_w->_mp_num._mp_size;
}
# 1836 "../gmp.h"
#define __GMPN_AORS(cout,wp,xp,xsize,yp,ysize,FUNCTION,TEST) do { mp_size_t __gmp_i; mp_limb_t __gmp_x; __gmp_i = (ysize); if (__gmp_i != 0) { if (FUNCTION (wp, xp, yp, __gmp_i)) { do { if (__gmp_i >= (xsize)) { (cout) = 1; goto __gmp_done; } __gmp_x = (xp)[__gmp_i]; } while (TEST); } } if ((wp) != (xp)) __GMPN_COPY_REST (wp, xp, xsize, __gmp_i); (cout) = 0; __gmp_done: ; } while (0)
# 1870 "../gmp.h"
#define __GMPN_ADD(cout,wp,xp,xsize,yp,ysize) __GMPN_AORS (cout, wp, xp, xsize, yp, ysize, mpn_add_n, (((wp)[__gmp_i++] = (__gmp_x + 1) & GMP_NUMB_MASK) == 0))


#define __GMPN_SUB(cout,wp,xp,xsize,yp,ysize) __GMPN_AORS (cout, wp, xp, xsize, yp, ysize, mpn_sub_n, (((wp)[__gmp_i++] = (__gmp_x - 1) & GMP_NUMB_MASK), __gmp_x == 0))
# 1903 "../gmp.h"
#define __GMPN_AORS_1(cout,dst,src,n,v,OP,CB) do { mp_size_t __gmp_i; mp_limb_t __gmp_x, __gmp_r; __gmp_x = (src)[0]; __gmp_r = __gmp_x OP (v); (dst)[0] = __gmp_r; if (CB (__gmp_r, __gmp_x, (v))) { (cout) = 1; for (__gmp_i = 1; __gmp_i < (n);) { __gmp_x = (src)[__gmp_i]; __gmp_r = __gmp_x OP 1; (dst)[__gmp_i] = __gmp_r; ++__gmp_i; if (!CB (__gmp_r, __gmp_x, 1)) { if ((src) != (dst)) __GMPN_COPY_REST (dst, src, n, __gmp_i); (cout) = 0; break; } } } else { if ((src) != (dst)) __GMPN_COPY_REST (dst, src, n, 1); (cout) = 0; } } while (0)
# 1980 "../gmp.h"
#define __GMPN_ADDCB(r,x,y) ((r) < (y))
#define __GMPN_SUBCB(r,x,y) ((x) < (y))

#define __GMPN_ADD_1(cout,dst,src,n,v) __GMPN_AORS_1(cout, dst, src, n, v, +, __GMPN_ADDCB)

#define __GMPN_SUB_1(cout,dst,src,n,v) __GMPN_AORS_1(cout, dst, src, n, v, -, __GMPN_SUBCB)






#define __GMPN_CMP(result,xp,yp,size) do { mp_size_t __gmp_i; mp_limb_t __gmp_x, __gmp_y; (result) = 0; __gmp_i = (size); while (--__gmp_i >= 0) { __gmp_x = (xp)[__gmp_i]; __gmp_y = (yp)[__gmp_i]; if (__gmp_x != __gmp_y) { (result) = (__gmp_x > __gmp_y ? 1 : -1); break; } } } while (0)
# 2028 "../gmp.h"
#define __GMPN_COPY_REST(dst,src,size,start) do { mp_size_t __gmp_j; __GMP_CRAY_Pragma ("_CRI ivdep"); for (__gmp_j = (start); __gmp_j < (size); __gmp_j++) (dst)[__gmp_j] = (src)[__gmp_j]; } while (0)
# 2046 "../gmp.h"
#define __GMPN_COPY(dst,src,size) __GMPN_COPY_REST (dst, src, size, 0)





extern __inline__ __attribute__ ((__gnu_inline__))

mp_limb_t
__gmpn_add (mp_ptr __gmp_wp, mp_srcptr __gmp_xp, mp_size_t __gmp_xsize, mp_srcptr __gmp_yp, mp_size_t __gmp_ysize)
{
  mp_limb_t __gmp_c;
  do { mp_size_t __gmp_i; mp_limb_t __gmp_x; __gmp_i = (__gmp_ysize); if (__gmp_i != 0) { if (__gmpn_add_n (__gmp_wp, __gmp_xp, __gmp_yp, __gmp_i)) { do { if (__gmp_i >= (__gmp_xsize)) { (__gmp_c) = 1; goto __gmp_done; } __gmp_x = (__gmp_xp)[__gmp_i]; } while ((((__gmp_wp)[__gmp_i++] = (__gmp_x + 1) & ((~ ((mp_limb_t) (0))) >> 0)) == 0)); } } if ((__gmp_wp) != (__gmp_xp)) do { mp_size_t __gmp_j; ; for (__gmp_j = (__gmp_i); __gmp_j < (__gmp_xsize); __gmp_j++) (__gmp_wp)[__gmp_j] = (__gmp_xp)[__gmp_j]; } while (0); (__gmp_c) = 0; __gmp_done: ; } while (0);
  return __gmp_c;
}




extern __inline__ __attribute__ ((__gnu_inline__))

mp_limb_t
__gmpn_add_1 (mp_ptr __gmp_dst, mp_srcptr __gmp_src, mp_size_t __gmp_size, mp_limb_t __gmp_n)
{
  mp_limb_t __gmp_c;
  do { mp_size_t __gmp_i; mp_limb_t __gmp_x, __gmp_r; __gmp_x = (__gmp_src)[0]; __gmp_r = __gmp_x + (__gmp_n); (__gmp_dst)[0] = __gmp_r; if (((__gmp_r) < ((__gmp_n)))) { (__gmp_c) = 1; for (__gmp_i = 1; __gmp_i < (__gmp_size);) { __gmp_x = (__gmp_src)[__gmp_i]; __gmp_r = __gmp_x + 1; (__gmp_dst)[__gmp_i] = __gmp_r; ++__gmp_i; if (!((__gmp_r) < (1))) { if ((__gmp_src) != (__gmp_dst)) do { mp_size_t __gmp_j; ; for (__gmp_j = (__gmp_i); __gmp_j < (__gmp_size); __gmp_j++) (__gmp_dst)[__gmp_j] = (__gmp_src)[__gmp_j]; } while (0); (__gmp_c) = 0; break; } } } else { if ((__gmp_src) != (__gmp_dst)) do { mp_size_t __gmp_j; ; for (__gmp_j = (1); __gmp_j < (__gmp_size); __gmp_j++) (__gmp_dst)[__gmp_j] = (__gmp_src)[__gmp_j]; } while (0); (__gmp_c) = 0; } } while (0);
  return __gmp_c;
}




extern __inline__ __attribute__ ((__gnu_inline__))

int
__gmpn_cmp (mp_srcptr __gmp_xp, mp_srcptr __gmp_yp, mp_size_t __gmp_size)
{
  int __gmp_result;
  do { mp_size_t __gmp_i; mp_limb_t __gmp_x, __gmp_y; (__gmp_result) = 0; __gmp_i = (__gmp_size); while (--__gmp_i >= 0) { __gmp_x = (__gmp_xp)[__gmp_i]; __gmp_y = (__gmp_yp)[__gmp_i]; if (__gmp_x != __gmp_y) { (__gmp_result) = (__gmp_x > __gmp_y ? 1 : -1); break; } } } while (0);
  return __gmp_result;
}




extern __inline__ __attribute__ ((__gnu_inline__))

mp_limb_t
__gmpn_sub (mp_ptr __gmp_wp, mp_srcptr __gmp_xp, mp_size_t __gmp_xsize, mp_srcptr __gmp_yp, mp_size_t __gmp_ysize)
{
  mp_limb_t __gmp_c;
  do { mp_size_t __gmp_i; mp_limb_t __gmp_x; __gmp_i = (__gmp_ysize); if (__gmp_i != 0) { if (__gmpn_sub_n (__gmp_wp, __gmp_xp, __gmp_yp, __gmp_i)) { do { if (__gmp_i >= (__gmp_xsize)) { (__gmp_c) = 1; goto __gmp_done; } __gmp_x = (__gmp_xp)[__gmp_i]; } while ((((__gmp_wp)[__gmp_i++] = (__gmp_x - 1) & ((~ ((mp_limb_t) (0))) >> 0)), __gmp_x == 0)); } } if ((__gmp_wp) != (__gmp_xp)) do { mp_size_t __gmp_j; ; for (__gmp_j = (__gmp_i); __gmp_j < (__gmp_xsize); __gmp_j++) (__gmp_wp)[__gmp_j] = (__gmp_xp)[__gmp_j]; } while (0); (__gmp_c) = 0; __gmp_done: ; } while (0);
  return __gmp_c;
}




extern __inline__ __attribute__ ((__gnu_inline__))

mp_limb_t
__gmpn_sub_1 (mp_ptr __gmp_dst, mp_srcptr __gmp_src, mp_size_t __gmp_size, mp_limb_t __gmp_n)
{
  mp_limb_t __gmp_c;
  do { mp_size_t __gmp_i; mp_limb_t __gmp_x, __gmp_r; __gmp_x = (__gmp_src)[0]; __gmp_r = __gmp_x - (__gmp_n); (__gmp_dst)[0] = __gmp_r; if (((__gmp_x) < ((__gmp_n)))) { (__gmp_c) = 1; for (__gmp_i = 1; __gmp_i < (__gmp_size);) { __gmp_x = (__gmp_src)[__gmp_i]; __gmp_r = __gmp_x - 1; (__gmp_dst)[__gmp_i] = __gmp_r; ++__gmp_i; if (!((__gmp_x) < (1))) { if ((__gmp_src) != (__gmp_dst)) do { mp_size_t __gmp_j; ; for (__gmp_j = (__gmp_i); __gmp_j < (__gmp_size); __gmp_j++) (__gmp_dst)[__gmp_j] = (__gmp_src)[__gmp_j]; } while (0); (__gmp_c) = 0; break; } } } else { if ((__gmp_src) != (__gmp_dst)) do { mp_size_t __gmp_j; ; for (__gmp_j = (1); __gmp_j < (__gmp_size); __gmp_j++) (__gmp_dst)[__gmp_j] = (__gmp_src)[__gmp_j]; } while (0); (__gmp_c) = 0; } } while (0);
  return __gmp_c;
}




extern __inline__ __attribute__ ((__gnu_inline__))

mp_limb_t
__gmpn_neg (mp_ptr __gmp_rp, mp_srcptr __gmp_up, mp_size_t __gmp_n)
{
  mp_limb_t __gmp_ul, __gmp_cy;
  __gmp_cy = 0;
  do {
      __gmp_ul = *__gmp_up++;
      *__gmp_rp++ = -__gmp_ul - __gmp_cy;
      __gmp_cy |= __gmp_ul != 0;
  } while (--__gmp_n != 0);
  return __gmp_cy;
}
# 2139 "../gmp.h"
#define mpz_sgn(Z) ((Z)->_mp_size < 0 ? -1 : (Z)->_mp_size > 0)
#define mpf_sgn(F) ((F)->_mp_size < 0 ? -1 : (F)->_mp_size > 0)
#define mpq_sgn(Q) ((Q)->_mp_num._mp_size < 0 ? -1 : (Q)->_mp_num._mp_size > 0)



#define mpz_cmp_ui(Z,UI) (__builtin_constant_p (UI) && (UI) == 0 ? mpz_sgn (Z) : _mpz_cmp_ui (Z,UI))


#define mpz_cmp_si(Z,SI) (__builtin_constant_p (SI) && (SI) == 0 ? mpz_sgn (Z) : __builtin_constant_p (SI) && (SI) > 0 ? _mpz_cmp_ui (Z, __GMP_CAST (unsigned long int, SI)) : _mpz_cmp_si (Z,SI))




#define mpq_cmp_ui(Q,NUI,DUI) (__builtin_constant_p (NUI) && (NUI) == 0 ? mpq_sgn (Q) : _mpq_cmp_ui (Q,NUI,DUI))


#define mpq_cmp_si(q,n,d) (__builtin_constant_p ((n) >= 0) && (n) >= 0 ? mpq_cmp_ui (q, __GMP_CAST (unsigned long, n), d) : _mpq_cmp_si (q, n, d))
# 2171 "../gmp.h"
#define mpz_odd_p(z) (((z)->_mp_size != 0) & __GMP_CAST (int, (z)->_mp_d[0]))
#define mpz_even_p(z) (! mpz_odd_p (z))
# 2188 "../gmp.h"
#define mpn_divmod(qp,np,nsize,dp,dsize) mpn_divrem (qp, __GMP_CAST (mp_size_t, 0), np, nsize, dp, dsize)



#define mpz_mdiv mpz_fdiv_q
#define mpz_mdivmod mpz_fdiv_qr
#define mpz_mmod mpz_fdiv_r
#define mpz_mdiv_ui mpz_fdiv_q_ui
#define mpz_mdivmod_ui(q,r,n,d) (((r) == 0) ? mpz_fdiv_q_ui (q,n,d) : mpz_fdiv_qr_ui (q,r,n,d))

#define mpz_mmod_ui(r,n,d) (((r) == 0) ? mpz_fdiv_ui (n,d) : mpz_fdiv_r_ui (r,n,d))



#define mpz_div mpz_fdiv_q
#define mpz_divmod mpz_fdiv_qr
#define mpz_div_ui mpz_fdiv_q_ui
#define mpz_divmod_ui mpz_fdiv_qr_ui
#define mpz_div_2exp mpz_fdiv_q_2exp
#define mpz_mod_2exp mpz_fdiv_r_2exp

enum
{
  GMP_ERROR_NONE = 0,
  GMP_ERROR_UNSUPPORTED_ARGUMENT = 1,
  GMP_ERROR_DIVISION_BY_ZERO = 2,
  GMP_ERROR_SQRT_OF_NEGATIVE = 4,
  GMP_ERROR_INVALID_ARGUMENT = 8
};


#define __GMP_CC "x86_64-pc-linux-gnu-gcc -std=gnu99"
#define __GMP_CFLAGS "-O2 -march=native -pipe"


#define __GNU_MP_VERSION 5
#define __GNU_MP_VERSION_MINOR 1
#define __GNU_MP_VERSION_PATCHLEVEL 1
#define __GNU_MP_RELEASE (__GNU_MP_VERSION * 10000 + __GNU_MP_VERSION_MINOR * 100 + __GNU_MP_VERSION_PATCHLEVEL)

#define __GMP_H__ 
# 25 "hgcd_appr.c" 2
# 1 "../gmp-impl.h" 1
# 35 "../gmp-impl.h"
#define __GMP_IMPL_H__ 
# 59 "../gmp-impl.h"
#define DECL_add_n(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t)

#define DECL_addlsh1_n(name) DECL_add_n (name)

#define DECL_addlsh2_n(name) DECL_add_n (name)

#define DECL_addmul_1(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_addmul_2(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr)

#define DECL_bdiv_dbm1c(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t)

#define DECL_com(name) __GMP_DECLSPEC void name (mp_ptr, mp_srcptr, mp_size_t)

#define DECL_copyd(name) __GMP_DECLSPEC void name (mp_ptr, mp_srcptr, mp_size_t)

#define DECL_copyi(name) DECL_copyd (name)

#define DECL_divexact_1(name) __GMP_DECLSPEC void name (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_divexact_by3c(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_divrem_1(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_gcd_1(name) __GMP_DECLSPEC mp_limb_t name (mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_lshift(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_srcptr, mp_size_t, unsigned)

#define DECL_lshiftc(name) DECL_lshift (name)

#define DECL_mod_1(name) __GMP_DECLSPEC mp_limb_t name (mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_mod_1_1p(name) __GMP_DECLSPEC mp_limb_t name (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [])

#define DECL_mod_1_1p_cps(name) __GMP_DECLSPEC void name (mp_limb_t cps[], mp_limb_t b)

#define DECL_mod_1s_2p(name) DECL_mod_1_1p (name)

#define DECL_mod_1s_2p_cps(name) DECL_mod_1_1p_cps (name)

#define DECL_mod_1s_4p(name) DECL_mod_1_1p (name)

#define DECL_mod_1s_4p_cps(name) DECL_mod_1_1p_cps (name)

#define DECL_mod_34lsub1(name) __GMP_DECLSPEC mp_limb_t name (mp_srcptr, mp_size_t)

#define DECL_modexact_1c_odd(name) __GMP_DECLSPEC mp_limb_t name (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t)

#define DECL_mul_1(name) DECL_addmul_1 (name)

#define DECL_mul_basecase(name) __GMP_DECLSPEC void name (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t)

#define DECL_mullo_basecase(name) __GMP_DECLSPEC void name (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t)

#define DECL_preinv_divrem_1(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int)

#define DECL_preinv_mod_1(name) __GMP_DECLSPEC mp_limb_t name (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t)

#define DECL_redc_1(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t)

#define DECL_redc_2(name) __GMP_DECLSPEC mp_limb_t name (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr)

#define DECL_rshift(name) DECL_lshift (name)

#define DECL_sqr_basecase(name) __GMP_DECLSPEC void name (mp_ptr, mp_srcptr, mp_size_t)

#define DECL_sub_n(name) DECL_add_n (name)

#define DECL_sublsh1_n(name) DECL_add_n (name)

#define DECL_submul_1(name) DECL_addmul_1 (name)



# 1 "../config.h" 1
# 30 "../config.h"
#define GMP_MPARAM_H_SUGGEST "./mpn/x86_64/k8/gmp-mparam.h"


#define HAVE_ALARM 1


#define HAVE_ALLOCA 1



#define HAVE_ALLOCA_H 1


#define HAVE_ATTRIBUTE_CONST 1


#define HAVE_ATTRIBUTE_MALLOC 1



#define HAVE_ATTRIBUTE_MODE 1


#define HAVE_ATTRIBUTE_NORETURN 1






#define HAVE_CALLING_CONVENTIONS 1


#define HAVE_CLOCK 1


#define HAVE_CLOCK_GETTIME 1






#define HAVE_DECL_FGETC 1



#define HAVE_DECL_FSCANF 1



#define HAVE_DECL_OPTARG 1



#define HAVE_DECL_SYS_ERRLIST 1



#define HAVE_DECL_SYS_NERR 1



#define HAVE_DECL_UNGETC 1



#define HAVE_DECL_VFPRINTF 1


#define HAVE_DLFCN_H 1







#define HAVE_DOUBLE_IEEE_LITTLE_ENDIAN 1






#define HAVE_FCNTL_H 1


#define HAVE_FLOAT_H 1


#define HAVE_GETPAGESIZE 1


#define HAVE_GETRUSAGE 1





#define HAVE_GETTIMEOFDAY 1
# 140 "../config.h"
#define HAVE_HOST_CPU_FAMILY_x86_64 1
# 175 "../config.h"
#define HAVE_INTMAX_T 1


#define HAVE_INTPTR_T 1


#define HAVE_INTTYPES_H 1





#define HAVE_LANGINFO_H 1





#define HAVE_LIMB_LITTLE_ENDIAN 1


#define HAVE_LOCALECONV 1


#define HAVE_LOCALE_H 1


#define HAVE_LONG_DOUBLE 1


#define HAVE_LONG_LONG 1





#define HAVE_MEMORY_H 1


#define HAVE_MEMSET 1


#define HAVE_MMAP 1


#define HAVE_MPROTECT 1



#define HAVE_NATIVE_mpn_add_n 1

#define HAVE_NATIVE_mpn_add_nc 1
#define HAVE_NATIVE_mpn_addaddmul_1msb0 1
#define HAVE_NATIVE_mpn_addcnd_n 1
#define HAVE_NATIVE_mpn_addlsh1_n 1
#define HAVE_NATIVE_mpn_addlsh2_n 1
#define HAVE_NATIVE_mpn_addlsh_n 1
# 248 "../config.h"
#define HAVE_NATIVE_mpn_addmul_2 1







#define HAVE_NATIVE_mpn_and_n 1
#define HAVE_NATIVE_mpn_andn_n 1
#define HAVE_NATIVE_mpn_bdiv_dbm1c 1
#define HAVE_NATIVE_mpn_bdiv_q_1 1
#define HAVE_NATIVE_mpn_pi1_bdiv_q_1 1
#define HAVE_NATIVE_mpn_com 1
#define HAVE_NATIVE_mpn_copyd 1
#define HAVE_NATIVE_mpn_copyi 1

#define HAVE_NATIVE_mpn_divexact_1 1

#define HAVE_NATIVE_mpn_divrem_1 1

#define HAVE_NATIVE_mpn_divrem_2 1
#define HAVE_NATIVE_mpn_gcd_1 1
#define HAVE_NATIVE_mpn_hamdist 1
#define HAVE_NATIVE_mpn_invert_limb 1
#define HAVE_NATIVE_mpn_ior_n 1
#define HAVE_NATIVE_mpn_iorn_n 1
#define HAVE_NATIVE_mpn_lshift 1
#define HAVE_NATIVE_mpn_lshiftc 1


#define HAVE_NATIVE_mpn_mod_1_1p 1

#define HAVE_NATIVE_mpn_mod_1s_2p 1
#define HAVE_NATIVE_mpn_mod_1s_4p 1
#define HAVE_NATIVE_mpn_mod_34lsub1 1
#define HAVE_NATIVE_mpn_modexact_1_odd 1
#define HAVE_NATIVE_mpn_modexact_1c_odd 1
#define HAVE_NATIVE_mpn_mul_1 1
#define HAVE_NATIVE_mpn_mul_1c 1
#define HAVE_NATIVE_mpn_mul_2 1




#define HAVE_NATIVE_mpn_mul_basecase 1
#define HAVE_NATIVE_mpn_nand_n 1
#define HAVE_NATIVE_mpn_nior_n 1
#define HAVE_NATIVE_mpn_popcount 1
#define HAVE_NATIVE_mpn_preinv_divrem_1 1

#define HAVE_NATIVE_mpn_redc_1 1

#define HAVE_NATIVE_mpn_rsblsh1_n 1
#define HAVE_NATIVE_mpn_rsblsh2_n 1
#define HAVE_NATIVE_mpn_rsblsh_n 1



#define HAVE_NATIVE_mpn_rsh1add_n 1
#define HAVE_NATIVE_mpn_rsh1add_nc 1
#define HAVE_NATIVE_mpn_rsh1sub_n 1
#define HAVE_NATIVE_mpn_rsh1sub_nc 1
#define HAVE_NATIVE_mpn_rshift 1
#define HAVE_NATIVE_mpn_sqr_basecase 1


#define HAVE_NATIVE_mpn_sub_n 1
#define HAVE_NATIVE_mpn_sub_nc 1
#define HAVE_NATIVE_mpn_subcnd_n 1
#define HAVE_NATIVE_mpn_sublsh1_n 1
# 331 "../config.h"
#define HAVE_NATIVE_mpn_tabselect 1




#define HAVE_NATIVE_mpn_xor_n 1
#define HAVE_NATIVE_mpn_xnor_n 1


#define HAVE_NL_LANGINFO 1


#define HAVE_NL_TYPES_H 1


#define HAVE_OBSTACK_VPRINTF 1


#define HAVE_POPEN 1
# 362 "../config.h"
#define HAVE_PTRDIFF_T 1


#define HAVE_QUAD_T 1


#define HAVE_RAISE 1





#define HAVE_SIGACTION 1


#define HAVE_SIGALTSTACK 1


#define HAVE_SIGSTACK 1


#define HAVE_SPEED_CYCLECOUNTER 2


#define HAVE_SSTREAM 1


#define HAVE_STACK_T 1


#define HAVE_STDARG 1


#define HAVE_STDINT_H 1


#define HAVE_STDLIB_H 1


#define HAVE_STD__LOCALE 1


#define HAVE_STRCHR 1


#define HAVE_STRERROR 1


#define HAVE_STRINGIZE 1


#define HAVE_STRINGS_H 1


#define HAVE_STRING_H 1


#define HAVE_STRNLEN 1


#define HAVE_STRTOL 1


#define HAVE_STRTOUL 1


#define HAVE_SYSCONF 1


#define HAVE_SYSCTL 1
# 446 "../config.h"
#define HAVE_SYS_MMAN_H 1


#define HAVE_SYS_PARAM_H 1
# 458 "../config.h"
#define HAVE_SYS_RESOURCE_H 1


#define HAVE_SYS_STAT_H 1


#define HAVE_SYS_SYSCTL_H 1


#define HAVE_SYS_SYSINFO_H 1
# 476 "../config.h"
#define HAVE_SYS_TIMES_H 1


#define HAVE_SYS_TIME_H 1


#define HAVE_SYS_TYPES_H 1


#define HAVE_TIMES 1


#define HAVE_UINT_LEAST32_T 1


#define HAVE_UNISTD_H 1


#define HAVE_VSNPRINTF 1





#define LSYM_PREFIX ".L"



#define LT_OBJDIR ".libs/"


#define PACKAGE "gmp"


#define PACKAGE_BUGREPORT "[e-mail], see http://gmplib.org/manual/Reporting-Bugs.html"


#define PACKAGE_NAME "GNU MP"


#define PACKAGE_STRING "GNU MP 5.1.1"


#define PACKAGE_TARNAME "gmp"


#define PACKAGE_URL "http://www.gnu.org/software/gmp/"


#define PACKAGE_VERSION "5.1.1"


#define RETSIGTYPE void


#define SIZEOF_MP_LIMB_T 8


#define SIZEOF_UNSIGNED 4


#define SIZEOF_UNSIGNED_LONG 8


#define SIZEOF_UNSIGNED_SHORT 2


#define SIZEOF_VOID_P 8





#define STDC_HEADERS 1


#define TIME_WITH_SYS_TIME 1





#define VERSION "5.1.1"
# 567 "../config.h"
#define WANT_FFT 1
# 584 "../config.h"
#define WANT_TMP_ALLOCA 1
# 603 "../config.h"
#define YYTEXT_POINTER 1
# 614 "../config.h"
#define restrict __restrict
# 134 "../gmp-impl.h" 2
# 1 "../gmp-mparam.h" 1


#define MOD_1_NORM_THRESHOLD 0
#define MOD_1_UNNORM_THRESHOLD 0
#define MOD_1N_TO_MOD_1_1_THRESHOLD 3
#define MOD_1U_TO_MOD_1_1_THRESHOLD 3
#define MOD_1_1_TO_MOD_1_2_THRESHOLD 9
#define MOD_1_2_TO_MOD_1_4_THRESHOLD 22
#define PREINV_MOD_1_TO_MOD_1_THRESHOLD 10
#define USE_PREINV_DIVREM_1 1
#define DIV_QR_2_PI2_THRESHOLD MP_SIZE_T_MAX
#define DIVEXACT_1_THRESHOLD 0
#define BMOD_1_TO_MOD_1_THRESHOLD 30

#define MUL_TOOM22_THRESHOLD 18
#define MUL_TOOM33_THRESHOLD 65
#define MUL_TOOM44_THRESHOLD 178
#define MUL_TOOM6H_THRESHOLD 298
#define MUL_TOOM8H_THRESHOLD 357

#define MUL_TOOM32_TO_TOOM43_THRESHOLD 106
#define MUL_TOOM32_TO_TOOM53_THRESHOLD 131
#define MUL_TOOM42_TO_TOOM53_THRESHOLD 121
#define MUL_TOOM42_TO_TOOM63_THRESHOLD 151
#define MUL_TOOM43_TO_TOOM54_THRESHOLD 166

#define SQR_BASECASE_THRESHOLD 0
#define SQR_TOOM2_THRESHOLD 30
#define SQR_TOOM3_THRESHOLD 105
#define SQR_TOOM4_THRESHOLD 396
#define SQR_TOOM6_THRESHOLD 0
#define SQR_TOOM8_THRESHOLD 502

#define MULMID_TOOM42_THRESHOLD 24

#define MULMOD_BNM1_THRESHOLD 14
#define SQRMOD_BNM1_THRESHOLD 15

#define MUL_FFT_MODF_THRESHOLD 444
#define MUL_FFT_TABLE3 { { 444, 5}, { 19, 6}, { 20, 7}, { 11, 6}, { 23, 7}, { 21, 8}, { 11, 7}, { 25, 8}, { 13, 7}, { 27, 8}, { 15, 7}, { 31, 8}, { 17, 7}, { 35, 8}, { 19, 7}, { 39, 8}, { 21, 9}, { 11, 8}, { 27, 9}, { 15, 8}, { 35, 9}, { 19, 8}, { 39, 9}, { 23, 8}, { 47, 9}, { 27,10}, { 15, 9}, { 31, 8}, { 63, 9}, { 39,10}, { 23, 9}, { 51,11}, { 15,10}, { 31, 9}, { 67, 5}, { 1087, 4}, { 2175, 5}, { 1151, 7}, { 303, 6}, { 607, 8}, { 153, 6}, { 639, 8}, { 163, 7}, { 351, 8}, { 177, 9}, { 95,10}, { 1024,11}, { 2048,12}, { 4096,13}, { 8192,14}, { 16384,15}, { 32768,16}, { 65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
# 56 "../gmp-mparam.h"
#define MUL_FFT_TABLE3_SIZE 60
#define MUL_FFT_THRESHOLD 3712

#define SQR_FFT_MODF_THRESHOLD 336
#define SQR_FFT_TABLE3 { { 336, 5}, { 17, 6}, { 9, 5}, { 19, 6}, { 10, 5}, { 21, 6}, { 21, 7}, { 11, 6}, { 23, 7}, { 21, 8}, { 11, 7}, { 24, 8}, { 13, 7}, { 27, 8}, { 15, 7}, { 31, 8}, { 19, 7}, { 39, 8}, { 21, 9}, { 11, 8}, { 27, 9}, { 15, 8}, { 33, 9}, { 19, 8}, { 39, 9}, { 23, 8}, { 47, 9}, { 27,10}, { 15, 9}, { 39,10}, { 23, 9}, { 47,11}, { 15,10}, { 31, 9}, { 63,10}, { 39, 9}, { 79,10}, { 47,11}, { 2048,12}, { 4096,13}, { 8192,14}, { 16384,15}, { 32768,16}, { 65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
# 74 "../gmp-mparam.h"
#define SQR_FFT_TABLE3_SIZE 51
#define SQR_FFT_THRESHOLD 3264

#define MULLO_BASECASE_THRESHOLD 0
#define MULLO_DC_THRESHOLD 54
#define MULLO_MUL_N_THRESHOLD 6633

#define DC_DIV_QR_THRESHOLD 39
#define DC_DIVAPPR_Q_THRESHOLD 143
#define DC_BDIV_QR_THRESHOLD 39
#define DC_BDIV_Q_THRESHOLD 76

#define INV_MULMOD_BNM1_THRESHOLD 34
#define INV_NEWTON_THRESHOLD 155
#define INV_APPR_THRESHOLD 147

#define BINV_NEWTON_THRESHOLD 204
#define REDC_1_TO_REDC_2_THRESHOLD 16
#define REDC_2_TO_REDC_N_THRESHOLD 55

#define MU_DIV_QR_THRESHOLD 1499
#define MU_DIVAPPR_Q_THRESHOLD 1589
#define MUPI_DIV_QR_THRESHOLD 73
#define MU_BDIV_QR_THRESHOLD 1187
#define MU_BDIV_Q_THRESHOLD 1499

#define POWM_SEC_TABLE 4,53,453,961,2178

#define MATRIX22_STRASSEN_THRESHOLD 21
#define HGCD_THRESHOLD 
# 135 "../gmp-impl.h" 2
# 1 "../fib_table.h" 1






#define FIB_TABLE_LIMIT 93
#define FIB_TABLE_LUCNUM_LIMIT 92
# 136 "../gmp-impl.h" 2
# 1 "../fac_table.h" 1






#define ONE_LIMB_FACTORIAL_TABLE CNST_LIMB(0x1),CNST_LIMB(0x1),CNST_LIMB(0x2),CNST_LIMB(0x6),CNST_LIMB(0x18),CNST_LIMB(0x78),CNST_LIMB(0x2d0),CNST_LIMB(0x13b0),CNST_LIMB(0x9d80),CNST_LIMB(0x58980),CNST_LIMB(0x375f00),CNST_LIMB(0x2611500),CNST_LIMB(0x1c8cfc00),CNST_LIMB(0x17328cc00),CNST_LIMB(0x144c3b2800),CNST_LIMB(0x13077775800),CNST_LIMB(0x130777758000),CNST_LIMB(0x1437eeecd8000),CNST_LIMB(0x16beecca730000),CNST_LIMB(0x1b02b9306890000),CNST_LIMB(0x21c3677c82b40000)



#define ONE_LIMB_ODD_FACTORIAL_TABLE CNST_LIMB(0x1),CNST_LIMB(0x1),CNST_LIMB(0x1),CNST_LIMB(0x3),CNST_LIMB(0x3),CNST_LIMB(0xf),CNST_LIMB(0x2d),CNST_LIMB(0x13b),CNST_LIMB(0x13b),CNST_LIMB(0xb13),CNST_LIMB(0x375f),CNST_LIMB(0x26115),CNST_LIMB(0x7233f),CNST_LIMB(0x5cca33),CNST_LIMB(0x2898765),CNST_LIMB(0x260eeeeb),CNST_LIMB(0x260eeeeb),CNST_LIMB(0x286fddd9b),CNST_LIMB(0x16beecca73),CNST_LIMB(0x1b02b930689),CNST_LIMB(0x870d9df20ad),CNST_LIMB(0xb141df4dae31),CNST_LIMB(0x79dd498567c1b),CNST_LIMB(0xaf2e19afc5266d),CNST_LIMB(0x20d8a4d0f4f7347),CNST_LIMB(0x335281867ec241ef)
#define ODD_FACTORIAL_TABLE_MAX CNST_LIMB(0x335281867ec241ef)
#define ODD_FACTORIAL_TABLE_LIMIT (25)


#define ONE_LIMB_ODD_FACTORIAL_EXTTABLE CNST_LIMB(0x9b3093d46fdd5923),CNST_LIMB(0x5e1f9767cc5866b1),CNST_LIMB(0x92dd23d6966aced7),CNST_LIMB(0xa30d0f4f0a196e5b),CNST_LIMB(0x8dc3e5a1977d7755),CNST_LIMB(0x2ab8ce915831734b),CNST_LIMB(0x2ab8ce915831734b),CNST_LIMB(0x81d2a0bc5e5fdcab),CNST_LIMB(0x9efcac82445da75b),CNST_LIMB(0xbc8b95cf58cde171),CNST_LIMB(0xa0e8444a1f3cecf9),CNST_LIMB(0x4191deb683ce3ffd),CNST_LIMB(0xddd3878bc84ebfc7),CNST_LIMB(0xcb39a64b83ff3751),CNST_LIMB(0xf8203f7993fc1495),CNST_LIMB(0xbd2a2a78b35f4bdd),CNST_LIMB(0x84757be6b6d13921),CNST_LIMB(0x3fbbcfc0b524988b),CNST_LIMB(0xbd11ed47c8928df9),CNST_LIMB(0x3c26b59e41c2f4c5),CNST_LIMB(0x677a5137e883fdb3),CNST_LIMB(0xff74e943b03b93dd),CNST_LIMB(0xfe5ebbcb10b2bb97),CNST_LIMB(0xb021f1de3235e7e7),CNST_LIMB(0x33509eb2e743a58f),CNST_LIMB(0x390f9da41279fb7d),CNST_LIMB(0xe5cb0154f031c559),CNST_LIMB(0x93074695ba4ddb6d),CNST_LIMB(0x81c471caa636247f),CNST_LIMB(0xe1347289b5a1d749),CNST_LIMB(0x286f21c3f76ce2ff),CNST_LIMB(0xbe84a2173e8ac7),CNST_LIMB(0x1595065ca215b88b),CNST_LIMB(0xf95877595b018809),CNST_LIMB(0x9c2efe3c5516f887),CNST_LIMB(0x373294604679382b),CNST_LIMB(0xaf1ff7a888adcd35),CNST_LIMB(0x18ddf279a2c5800b),CNST_LIMB(0x18ddf279a2c5800b),CNST_LIMB(0x505a90e2542582cb),CNST_LIMB(0x5bacad2cd8d5dc2b),CNST_LIMB(0xfe3152bcbff89f41)
#define ODD_FACTORIAL_EXTTABLE_LIMIT (67)


#define ONE_LIMB_ODD_DOUBLEFACTORIAL_TABLE CNST_LIMB(0x1),CNST_LIMB(0x3),CNST_LIMB(0xf),CNST_LIMB(0x69),CNST_LIMB(0x3b1),CNST_LIMB(0x289b),CNST_LIMB(0x20fdf),CNST_LIMB(0x1eee11),CNST_LIMB(0x20dcf21),CNST_LIMB(0x27065f73),CNST_LIMB(0x33385d46f),CNST_LIMB(0x49a10615f9),CNST_LIMB(0x730b9982551),CNST_LIMB(0xc223930bef8b),CNST_LIMB(0x15fe07a85a22bf),CNST_LIMB(0x2a9c2ed62ea3521),CNST_LIMB(0x57e22099c030d941)
#define ODD_DOUBLEFACTORIAL_TABLE_MAX CNST_LIMB(0x57e22099c030d941)
#define ODD_DOUBLEFACTORIAL_TABLE_LIMIT (33)


#define NTH_ROOT_NUMB_MASK_TABLE (GMP_NUMB_MASK),CNST_LIMB(0xffffffff),CNST_LIMB(0x285145),CNST_LIMB(0xffff),CNST_LIMB(0x1bdb),CNST_LIMB(0x659),CNST_LIMB(0x235),CNST_LIMB(0xff)




#define ONE_LIMB_ODD_FACTORIAL_INVERSES_TABLE CNST_LIMB(0x1),CNST_LIMB(0xaaaaaaaaaaaaaaab),CNST_LIMB(0xaaaaaaaaaaaaaaab),CNST_LIMB(0xeeeeeeeeeeeeeeef),CNST_LIMB(0x4fa4fa4fa4fa4fa5),CNST_LIMB(0x2ff2ff2ff2ff2ff3),CNST_LIMB(0x2ff2ff2ff2ff2ff3),CNST_LIMB(0x938cc70553e3771b),CNST_LIMB(0xb71c27cddd93e49f),CNST_LIMB(0xb38e3229fcdee63d),CNST_LIMB(0xe684bb63544a4cbf),CNST_LIMB(0xc2f684917ca340fb),CNST_LIMB(0xf747c9cba417526d),CNST_LIMB(0xbb26eb51d7bd49c3),CNST_LIMB(0xbb26eb51d7bd49c3),CNST_LIMB(0xb0a7efb985294093),CNST_LIMB(0xbe4b8c69f259eabb),CNST_LIMB(0x6854d17ed6dc4fb9),CNST_LIMB(0xe1aa904c915f4325),CNST_LIMB(0x3b8206df131cead1),CNST_LIMB(0x79c6009fea76fe13),CNST_LIMB(0xd8c5d381633cd365),CNST_LIMB(0x4841f12b21144677),CNST_LIMB(0x4a91ff68200b0d0f),CNST_LIMB(0x8f9513a58c4f9e8b),CNST_LIMB(0x2b3e690621a42251),CNST_LIMB(0x4f520f00e03c04e7),CNST_LIMB(0x2edf84ee600211d3),CNST_LIMB(0xadcaa2764aaacdfd),CNST_LIMB(0x161f4f9033f4fe63),CNST_LIMB(0x161f4f9033f4fe63),CNST_LIMB(0xbada2932ea4d3e03),CNST_LIMB(0xcec189f3efaa30d3),CNST_LIMB(0xf7475bb68330bf91),CNST_LIMB(0x37eb7bf7d5b01549),CNST_LIMB(0x46b35660a4e91555),CNST_LIMB(0xa567c12d81f151f7),CNST_LIMB(0x4c724007bb2071b1),CNST_LIMB(0xf4a0cce58a016bd),CNST_LIMB(0xfa21068e66106475),CNST_LIMB(0x244ab72b5a318ae1),CNST_LIMB(0x366ce67e080d0f23),CNST_LIMB(0xd666fdae5dd2a449),CNST_LIMB(0xd740ddd0acc06a0d),CNST_LIMB(0xb050bbbb28e6f97b),CNST_LIMB(0x70b003fe890a5c75),CNST_LIMB(0xd03aabff83037427),CNST_LIMB(0x13ec4ca72c783bd7),CNST_LIMB(0x90282c06afdbd96f),CNST_LIMB(0x4414ddb9db4a95d5),CNST_LIMB(0xa2c68735ae6832e9),CNST_LIMB(0xbf72d71455676665),CNST_LIMB(0xa8469fab6b759b7f),CNST_LIMB(0xc1e55b56e606caf9),CNST_LIMB(0x40455630fc4a1cff),CNST_LIMB(0x120a7b0046d16f7),CNST_LIMB(0xa7c3553b08faef23),CNST_LIMB(0x9f0bfd1b08d48639),CNST_LIMB(0xa433ffce9a304d37),CNST_LIMB(0xa22ad1d53915c683),CNST_LIMB(0xcb6cbc723ba5dd1d),CNST_LIMB(0x547fb1b8ab9d0ba3),CNST_LIMB(0x547fb1b8ab9d0ba3),CNST_LIMB(0x8f15a826498852e3)




#define TABLE_2N_MINUS_POPC_2N 1,3,4,7,8,10,11,15,16,18,19,22,23,25,26,31,32,34,35,38,39,41,42,46,47,49,50,53,54,56,57,63,64,66,67,70,71,73,74,78
#define TABLE_LIMIT_2N_MINUS_POPC_2N 81
#define ODD_CENTRAL_BINOMIAL_OFFSET (13)




#define ONE_LIMB_ODD_CENTRAL_BINOMIAL_TABLE CNST_LIMB(0x13d66b),CNST_LIMB(0x4c842f),CNST_LIMB(0x93ee7d),CNST_LIMB(0x11e9e123),CNST_LIMB(0x22c60053),CNST_LIMB(0x873ae4d1),CNST_LIMB(0x10757bd97),CNST_LIMB(0x80612c6cd),CNST_LIMB(0xfaa556bc1),CNST_LIMB(0x3d3cc24821),CNST_LIMB(0x77cfeb6bbb),CNST_LIMB(0x7550ebd97c7),CNST_LIMB(0xe5f08695caf),CNST_LIMB(0x386120ffce11),CNST_LIMB(0x6eabb28dd6df),CNST_LIMB(0x3658e31c82a8f),CNST_LIMB(0x6ad2050312783),CNST_LIMB(0x1a42902a5af0bf),CNST_LIMB(0x33ac44f881661d),CNST_LIMB(0xcb764f927d82123),CNST_LIMB(0x190c23fa46b93983),CNST_LIMB(0x62b7609e25caf1b9),CNST_LIMB(0xc29cb72925ef2cff)
#define ODD_CENTRAL_BINOMIAL_TABLE_LIMIT (35)


#define ONE_LIMB_ODD_CENTRAL_BINOMIAL_INVERSE_TABLE CNST_LIMB(0x61e5bd199bb12643),CNST_LIMB(0x78321494dc8342cf),CNST_LIMB(0x4fd348704ebf7ad5),CNST_LIMB(0x7e722ba086ab568b),CNST_LIMB(0xa5fcc124265843db),CNST_LIMB(0x89c4a6b18633f431),CNST_LIMB(0x4daa2c15f8ce9227),CNST_LIMB(0x801c618ca9be9605),CNST_LIMB(0x32dc192f948a441),CNST_LIMB(0xd02b90c2bf3be1),CNST_LIMB(0xd897e8c1749aa173),CNST_LIMB(0x54a234fc01fef9f7),CNST_LIMB(0x83ff2ab4d1ff7a4f),CNST_LIMB(0xa427f1c9b304e2f1),CNST_LIMB(0x9c14595d1793651f),CNST_LIMB(0x883a71c607a7b46f),CNST_LIMB(0xd089863c54bc9f2b),CNST_LIMB(0x9022f6bce5d07f3f),CNST_LIMB(0xbec207e218768c35),CNST_LIMB(0x9d70cb4cbb4f168b),CNST_LIMB(0x3c3d3403828a9d2b),CNST_LIMB(0x7672df58c56bc489),CNST_LIMB(0x1e66ca55d727d2ff)


#define CENTRAL_BINOMIAL_2FAC_TABLE 3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3
# 137 "../gmp-impl.h" 2
# 1 "../mp_bases.h" 1







#define MP_BASES_CHARS_PER_LIMB_10 19
#define MP_BASES_BIG_BASE_10 CNST_LIMB(0x8ac7230489e80000)
#define MP_BASES_BIG_BASE_INVERTED_10 CNST_LIMB(0xd83c94fb6d2ac34a)
#define MP_BASES_NORMALIZATION_STEPS_10 0
# 138 "../gmp-impl.h" 2






# 1 "/usr/include/inttypes.h" 1 3 4
# 23 "/usr/include/inttypes.h" 3 4
#define _INTTYPES_H 1

# 1 "/usr/include/features.h" 1 3 4
# 19 "/usr/include/features.h" 3 4
#define _FEATURES_H 1
# 98 "/usr/include/features.h" 3 4
#undef __USE_ISOC11
#undef __USE_ISOC99
#undef __USE_ISOC95
#undef __USE_ISOCXX11
#undef __USE_POSIX
#undef __USE_POSIX2
#undef __USE_POSIX199309
#undef __USE_POSIX199506
#undef __USE_XOPEN
#undef __USE_XOPEN_EXTENDED
#undef __USE_UNIX98
#undef __USE_XOPEN2K
#undef __USE_XOPEN2KXSI
#undef __USE_XOPEN2K8
#undef __USE_XOPEN2K8XSI
#undef __USE_LARGEFILE
#undef __USE_LARGEFILE64
#undef __USE_FILE_OFFSET64
#undef __USE_BSD
#undef __USE_SVID
#undef __USE_MISC
#undef __USE_ATFILE
#undef __USE_GNU
#undef __USE_REENTRANT
#undef __USE_FORTIFY_LEVEL
#undef __FAVOR_BSD
#undef __KERNEL_STRICT_NAMES




#define __KERNEL_STRICT_NAMES 



#define __USE_ANSI 1
# 143 "/usr/include/features.h" 3 4
#define __GNUC_PREREQ(maj,min) ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
# 188 "/usr/include/features.h" 3 4
#define _BSD_SOURCE 1
#define _SVID_SOURCE 1
# 201 "/usr/include/features.h" 3 4
#define __USE_ISOC99 1





#define __USE_ISOC95 1
# 223 "/usr/include/features.h" 3 4
#define _POSIX_SOURCE 1







#define _POSIX_C_SOURCE 200809L

#define __USE_POSIX_IMPLICITLY 1



#define __USE_POSIX 1



#define __USE_POSIX2 1



#define __USE_POSIX199309 1



#define __USE_POSIX199506 1



#define __USE_XOPEN2K 1
#undef __USE_ISOC95
#define __USE_ISOC95 1
#undef __USE_ISOC99
#define __USE_ISOC99 1



#define __USE_XOPEN2K8 1
#undef _ATFILE_SOURCE
#define _ATFILE_SOURCE 1
# 305 "/usr/include/features.h" 3 4
#define __USE_MISC 1



#define __USE_BSD 1



#define __USE_SVID 1



#define __USE_ATFILE 1
# 335 "/usr/include/features.h" 3 4
#define __USE_FORTIFY_LEVEL 2
# 346 "/usr/include/features.h" 3 4
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 19 "/usr/include/stdc-predef.h" 3 4
#define _STDC_PREDEF_H 1
# 30 "/usr/include/stdc-predef.h" 3 4
#define __STDC_IEC_559__ 1
#define __STDC_IEC_559_COMPLEX__ 1



#define __STDC_ISO_10646__ 201103L


#define __STDC_NO_THREADS__ 1
# 347 "/usr/include/features.h" 2 3 4







#undef __GNU_LIBRARY__
#define __GNU_LIBRARY__ 6



#define __GLIBC__ 2
#define __GLIBC_MINOR__ 17

#define __GLIBC_PREREQ(maj,min) ((__GLIBC__ << 16) + __GLIBC_MINOR__ >= ((maj) << 16) + (min))







#define __GLIBC_HAVE_LONG_LONG 1





# 1 "/usr/include/sys/cdefs.h" 1 3 4
# 20 "/usr/include/sys/cdefs.h" 3 4
#define _SYS_CDEFS_H 1
# 35 "/usr/include/sys/cdefs.h" 3 4
#undef __P
#undef __PMT






#define __LEAF , __leaf__
#define __LEAF_ATTR __attribute__ ((__leaf__))
# 56 "/usr/include/sys/cdefs.h" 3 4
#define __THROW __attribute__ ((__nothrow__ __LEAF))
#define __THROWNL __attribute__ ((__nothrow__))
#define __NTH(fct) __attribute__ ((__nothrow__ __LEAF)) fct
# 83 "/usr/include/sys/cdefs.h" 3 4
#define __P(args) args
#define __PMT(args) args




#define __CONCAT(x,y) x ## y
#define __STRING(x) #x


#define __ptr_t void *
#define __long_double_t long double







#define __BEGIN_DECLS 
#define __END_DECLS 
# 123 "/usr/include/sys/cdefs.h" 3 4
#define __BEGIN_NAMESPACE_STD 
#define __END_NAMESPACE_STD 
#define __USING_NAMESPACE_STD(name) 
#define __BEGIN_NAMESPACE_C99 
#define __END_NAMESPACE_C99 
#define __USING_NAMESPACE_C99(name) 





#define __bounded 
#define __unbounded 
#define __ptrvalue 




#define __bos(ptr) __builtin_object_size (ptr, __USE_FORTIFY_LEVEL > 1)
#define __bos0(ptr) __builtin_object_size (ptr, 0)
#define __fortify_function __extern_always_inline __attribute_artificial__


#define __warndecl(name,msg) extern void name (void) __attribute__((__warning__ (msg)))

#define __warnattr(msg) __attribute__((__warning__ (msg)))
#define __errordecl(name,msg) extern void name (void) __attribute__((__error__ (msg)))
# 160 "/usr/include/sys/cdefs.h" 3 4
#define __flexarr []
# 187 "/usr/include/sys/cdefs.h" 3 4
#define __REDIRECT(name,proto,alias) name proto __asm__ (__ASMNAME (#alias))






#define __REDIRECT_NTH(name,proto,alias) name proto __asm__ (__ASMNAME (#alias)) __THROW

#define __REDIRECT_NTHNL(name,proto,alias) name proto __asm__ (__ASMNAME (#alias)) __THROWNL


#define __ASMNAME(cname) __ASMNAME2 (__USER_LABEL_PREFIX__, cname)
#define __ASMNAME2(prefix,cname) __STRING (prefix) cname
# 221 "/usr/include/sys/cdefs.h" 3 4
#define __attribute_malloc__ __attribute__ ((__malloc__))
# 230 "/usr/include/sys/cdefs.h" 3 4
#define __attribute_pure__ __attribute__ ((__pure__))






#define __attribute_const__ __attribute__ ((__const__))
# 246 "/usr/include/sys/cdefs.h" 3 4
#define __attribute_used__ __attribute__ ((__used__))
#define __attribute_noinline__ __attribute__ ((__noinline__))







#define __attribute_deprecated__ __attribute__ ((__deprecated__))
# 267 "/usr/include/sys/cdefs.h" 3 4
#define __attribute_format_arg__(x) __attribute__ ((__format_arg__ (x)))
# 277 "/usr/include/sys/cdefs.h" 3 4
#define __attribute_format_strfmon__(a,b) __attribute__ ((__format__ (__strfmon__, a, b)))
# 286 "/usr/include/sys/cdefs.h" 3 4
#define __nonnull(params) __attribute__ ((__nonnull__ params))







#define __attribute_warn_unused_result__ __attribute__ ((__warn_unused_result__))


#define __wur __attribute_warn_unused_result__
# 308 "/usr/include/sys/cdefs.h" 3 4
#define __always_inline __inline __attribute__ ((__always_inline__))







#define __attribute_artificial__ __attribute__ ((__artificial__))
# 325 "/usr/include/sys/cdefs.h" 3 4
#define __extern_inline extern __inline __attribute__ ((__gnu_inline__))
#define __extern_always_inline extern __always_inline __attribute__ ((__gnu_inline__))
# 344 "/usr/include/sys/cdefs.h" 3 4
#define __va_arg_pack() __builtin_va_arg_pack ()
#define __va_arg_pack_len() __builtin_va_arg_pack_len ()
# 365 "/usr/include/sys/cdefs.h" 3 4
#define __restrict_arr __restrict
# 380 "/usr/include/sys/cdefs.h" 3 4
#define __glibc_unlikely(cond) __builtin_expect((cond), 0)




# 1 "/usr/include/bits/wordsize.h" 1 3 4



#define __WORDSIZE 64





#define __WORDSIZE_TIME64_COMPAT32 1

#define __SYSCALL_WORDSIZE 64
# 386 "/usr/include/sys/cdefs.h" 2 3 4
# 407 "/usr/include/sys/cdefs.h" 3 4
#define __LDBL_REDIR1(name,proto,alias) name proto
#define __LDBL_REDIR(name,proto) name proto
#define __LDBL_REDIR1_NTH(name,proto,alias) name proto __THROW
#define __LDBL_REDIR_NTH(name,proto) name proto __THROW
#define __LDBL_REDIR_DECL(name) 

#define __REDIRECT_LDBL(name,proto,alias) __REDIRECT (name, proto, alias)
#define __REDIRECT_NTH_LDBL(name,proto,alias) __REDIRECT_NTH (name, proto, alias)
# 377 "/usr/include/features.h" 2 3 4
# 392 "/usr/include/features.h" 3 4
#define __USE_EXTERN_INLINES 1







# 1 "/usr/include/gnu/stubs.h" 1 3 4
# 10 "/usr/include/gnu/stubs.h" 3 4
# 1 "/usr/include/gnu/stubs-64.h" 1 3 4
# 10 "/usr/include/gnu/stubs-64.h" 3 4
#define __stub_bdflush 
#define __stub_chflags 
#define __stub_fattach 
#define __stub_fchflags 
#define __stub_fdetach 
#define __stub_getmsg 
#define __stub_gtty 
#define __stub_lchmod 
#define __stub_putmsg 
#define __stub_revoke 
#define __stub_setlogin 
#define __stub_sigreturn 
#define __stub_sstk 
#define __stub_stty 
# 11 "/usr/include/gnu/stubs.h" 2 3 4
# 401 "/usr/include/features.h" 2 3 4
# 26 "/usr/include/inttypes.h" 2 3 4

# 1 "/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.2/include/stdint.h" 1 3 4


# 1 "/usr/include/stdint.h" 1 3 4
# 23 "/usr/include/stdint.h" 3 4
#define _STDINT_H 1


# 1 "/usr/include/bits/wchar.h" 1 3 4
# 20 "/usr/include/bits/wchar.h" 3 4
#define _BITS_WCHAR_H 1

# 1 "/usr/include/bits/wordsize.h" 1 3 4



#define __WORDSIZE 64





#define __WORDSIZE_TIME64_COMPAT32 1

#define __SYSCALL_WORDSIZE 64
# 23 "/usr/include/bits/wchar.h" 2 3 4


#define __WCHAR_MIN (-2147483647 - 1)
#define __WCHAR_MAX (2147483647)
# 27 "/usr/include/stdint.h" 2 3 4
# 1 "/usr/include/bits/wordsize.h" 1 3 4



#define __WORDSIZE 64





#define __WORDSIZE_TIME64_COMPAT32 1

#define __SYSCALL_WORDSIZE 64
# 28 "/usr/include/stdint.h" 2 3 4







#define __int8_t_defined 
typedef signed char int8_t;
typedef short int int16_t;
typedef int int32_t;

typedef long int int64_t;







typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;

typedef unsigned int uint32_t;
#define __uint32_t_defined 


typedef unsigned long int uint64_t;
# 65 "/usr/include/stdint.h" 3 4
typedef signed char int_least8_t;
typedef short int int_least16_t;
typedef int int_least32_t;

typedef long int int_least64_t;






typedef unsigned char uint_least8_t;
typedef unsigned short int uint_least16_t;
typedef unsigned int uint_least32_t;

typedef unsigned long int uint_least64_t;
# 90 "/usr/include/stdint.h" 3 4
typedef signed char int_fast8_t;

typedef long int int_fast16_t;
typedef long int int_fast32_t;
typedef long int int_fast64_t;
# 103 "/usr/include/stdint.h" 3 4
typedef unsigned char uint_fast8_t;

typedef unsigned long int uint_fast16_t;
typedef unsigned long int uint_fast32_t;
typedef unsigned long int uint_fast64_t;
# 119 "/usr/include/stdint.h" 3 4
typedef long int intptr_t;
#define __intptr_t_defined 

typedef unsigned long int uintptr_t;
# 134 "/usr/include/stdint.h" 3 4
typedef long int intmax_t;
typedef unsigned long int uintmax_t;
# 149 "/usr/include/stdint.h" 3 4
#define __INT64_C(c) c ## L
#define __UINT64_C(c) c ## UL
# 159 "/usr/include/stdint.h" 3 4
#define INT8_MIN (-128)
#define INT16_MIN (-32767-1)
#define INT32_MIN (-2147483647-1)
#define INT64_MIN (-__INT64_C(9223372036854775807)-1)

#define INT8_MAX (127)
#define INT16_MAX (32767)
#define INT32_MAX (2147483647)
#define INT64_MAX (__INT64_C(9223372036854775807))


#define UINT8_MAX (255)
#define UINT16_MAX (65535)
#define UINT32_MAX (4294967295U)
#define UINT64_MAX (__UINT64_C(18446744073709551615))



#define INT_LEAST8_MIN (-128)
#define INT_LEAST16_MIN (-32767-1)
#define INT_LEAST32_MIN (-2147483647-1)
#define INT_LEAST64_MIN (-__INT64_C(9223372036854775807)-1)

#define INT_LEAST8_MAX (127)
#define INT_LEAST16_MAX (32767)
#define INT_LEAST32_MAX (2147483647)
#define INT_LEAST64_MAX (__INT64_C(9223372036854775807))


#define UINT_LEAST8_MAX (255)
#define UINT_LEAST16_MAX (65535)
#define UINT_LEAST32_MAX (4294967295U)
#define UINT_LEAST64_MAX (__UINT64_C(18446744073709551615))



#define INT_FAST8_MIN (-128)

#define INT_FAST16_MIN (-9223372036854775807L-1)
#define INT_FAST32_MIN (-9223372036854775807L-1)




#define INT_FAST64_MIN (-__INT64_C(9223372036854775807)-1)

#define INT_FAST8_MAX (127)

#define INT_FAST16_MAX (9223372036854775807L)
#define INT_FAST32_MAX (9223372036854775807L)




#define INT_FAST64_MAX (__INT64_C(9223372036854775807))


#define UINT_FAST8_MAX (255)

#define UINT_FAST16_MAX (18446744073709551615UL)
#define UINT_FAST32_MAX (18446744073709551615UL)




#define UINT_FAST64_MAX (__UINT64_C(18446744073709551615))




#define INTPTR_MIN (-9223372036854775807L-1)
#define INTPTR_MAX (9223372036854775807L)
#define UINTPTR_MAX (18446744073709551615UL)
# 240 "/usr/include/stdint.h" 3 4
#define INTMAX_MIN (-__INT64_C(9223372036854775807)-1)

#define INTMAX_MAX (__INT64_C(9223372036854775807))


#define UINTMAX_MAX (__UINT64_C(18446744073709551615))






#define PTRDIFF_MIN (-9223372036854775807L-1)
#define PTRDIFF_MAX (9223372036854775807L)






#define SIG_ATOMIC_MIN (-2147483647-1)
#define SIG_ATOMIC_MAX (2147483647)



#define SIZE_MAX (18446744073709551615UL)







#define WCHAR_MIN __WCHAR_MIN
#define WCHAR_MAX __WCHAR_MAX



#define WINT_MIN (0u)
#define WINT_MAX (4294967295u)
# 289 "/usr/include/stdint.h" 3 4
#define INT8_C(c) c
#define INT16_C(c) c
#define INT32_C(c) c

#define INT64_C(c) c ## L





#define UINT8_C(c) c
#define UINT16_C(c) c
#define UINT32_C(c) c ## U

#define UINT64_C(c) c ## UL






#define INTMAX_C(c) c ## L
#define UINTMAX_C(c) c ## UL
# 4 "/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.2/include/stdint.h" 2 3 4



#define _GCC_WRAP_STDINT_H 
# 28 "/usr/include/inttypes.h" 2 3 4






typedef int __gwchar_t;





#define ____gwchar_t_defined 1
# 49 "/usr/include/inttypes.h" 3 4
#define __PRI64_PREFIX "l"
#define __PRIPTR_PREFIX "l"
# 59 "/usr/include/inttypes.h" 3 4
#define PRId8 "d"
#define PRId16 "d"
#define PRId32 "d"
#define PRId64 __PRI64_PREFIX "d"

#define PRIdLEAST8 "d"
#define PRIdLEAST16 "d"
#define PRIdLEAST32 "d"
#define PRIdLEAST64 __PRI64_PREFIX "d"

#define PRIdFAST8 "d"
#define PRIdFAST16 __PRIPTR_PREFIX "d"
#define PRIdFAST32 __PRIPTR_PREFIX "d"
#define PRIdFAST64 __PRI64_PREFIX "d"


#define PRIi8 "i"
#define PRIi16 "i"
#define PRIi32 "i"
#define PRIi64 __PRI64_PREFIX "i"

#define PRIiLEAST8 "i"
#define PRIiLEAST16 "i"
#define PRIiLEAST32 "i"
#define PRIiLEAST64 __PRI64_PREFIX "i"

#define PRIiFAST8 "i"
#define PRIiFAST16 __PRIPTR_PREFIX "i"
#define PRIiFAST32 __PRIPTR_PREFIX "i"
#define PRIiFAST64 __PRI64_PREFIX "i"


#define PRIo8 "o"
#define PRIo16 "o"
#define PRIo32 "o"
#define PRIo64 __PRI64_PREFIX "o"

#define PRIoLEAST8 "o"
#define PRIoLEAST16 "o"
#define PRIoLEAST32 "o"
#define PRIoLEAST64 __PRI64_PREFIX "o"

#define PRIoFAST8 "o"
#define PRIoFAST16 __PRIPTR_PREFIX "o"
#define PRIoFAST32 __PRIPTR_PREFIX "o"
#define PRIoFAST64 __PRI64_PREFIX "o"


#define PRIu8 "u"
#define PRIu16 "u"
#define PRIu32 "u"
#define PRIu64 __PRI64_PREFIX "u"

#define PRIuLEAST8 "u"
#define PRIuLEAST16 "u"
#define PRIuLEAST32 "u"
#define PRIuLEAST64 __PRI64_PREFIX "u"

#define PRIuFAST8 "u"
#define PRIuFAST16 __PRIPTR_PREFIX "u"
#define PRIuFAST32 __PRIPTR_PREFIX "u"
#define PRIuFAST64 __PRI64_PREFIX "u"


#define PRIx8 "x"
#define PRIx16 "x"
#define PRIx32 "x"
#define PRIx64 __PRI64_PREFIX "x"

#define PRIxLEAST8 "x"
#define PRIxLEAST16 "x"
#define PRIxLEAST32 "x"
#define PRIxLEAST64 __PRI64_PREFIX "x"

#define PRIxFAST8 "x"
#define PRIxFAST16 __PRIPTR_PREFIX "x"
#define PRIxFAST32 __PRIPTR_PREFIX "x"
#define PRIxFAST64 __PRI64_PREFIX "x"


#define PRIX8 "X"
#define PRIX16 "X"
#define PRIX32 "X"
#define PRIX64 __PRI64_PREFIX "X"

#define PRIXLEAST8 "X"
#define PRIXLEAST16 "X"
#define PRIXLEAST32 "X"
#define PRIXLEAST64 __PRI64_PREFIX "X"

#define PRIXFAST8 "X"
#define PRIXFAST16 __PRIPTR_PREFIX "X"
#define PRIXFAST32 __PRIPTR_PREFIX "X"
#define PRIXFAST64 __PRI64_PREFIX "X"



#define PRIdMAX __PRI64_PREFIX "d"
#define PRIiMAX __PRI64_PREFIX "i"
#define PRIoMAX __PRI64_PREFIX "o"
#define PRIuMAX __PRI64_PREFIX "u"
#define PRIxMAX __PRI64_PREFIX "x"
#define PRIXMAX __PRI64_PREFIX "X"



#define PRIdPTR __PRIPTR_PREFIX "d"
#define PRIiPTR __PRIPTR_PREFIX "i"
#define PRIoPTR __PRIPTR_PREFIX "o"
#define PRIuPTR __PRIPTR_PREFIX "u"
#define PRIxPTR __PRIPTR_PREFIX "x"
#define PRIXPTR __PRIPTR_PREFIX "X"





#define SCNd8 "hhd"
#define SCNd16 "hd"
#define SCNd32 "d"
#define SCNd64 __PRI64_PREFIX "d"

#define SCNdLEAST8 "hhd"
#define SCNdLEAST16 "hd"
#define SCNdLEAST32 "d"
#define SCNdLEAST64 __PRI64_PREFIX "d"

#define SCNdFAST8 "hhd"
#define SCNdFAST16 __PRIPTR_PREFIX "d"
#define SCNdFAST32 __PRIPTR_PREFIX "d"
#define SCNdFAST64 __PRI64_PREFIX "d"


#define SCNi8 "hhi"
#define SCNi16 "hi"
#define SCNi32 "i"
#define SCNi64 __PRI64_PREFIX "i"

#define SCNiLEAST8 "hhi"
#define SCNiLEAST16 "hi"
#define SCNiLEAST32 "i"
#define SCNiLEAST64 __PRI64_PREFIX "i"

#define SCNiFAST8 "hhi"
#define SCNiFAST16 __PRIPTR_PREFIX "i"
#define SCNiFAST32 __PRIPTR_PREFIX "i"
#define SCNiFAST64 __PRI64_PREFIX "i"


#define SCNu8 "hhu"
#define SCNu16 "hu"
#define SCNu32 "u"
#define SCNu64 __PRI64_PREFIX "u"

#define SCNuLEAST8 "hhu"
#define SCNuLEAST16 "hu"
#define SCNuLEAST32 "u"
#define SCNuLEAST64 __PRI64_PREFIX "u"

#define SCNuFAST8 "hhu"
#define SCNuFAST16 __PRIPTR_PREFIX "u"
#define SCNuFAST32 __PRIPTR_PREFIX "u"
#define SCNuFAST64 __PRI64_PREFIX "u"


#define SCNo8 "hho"
#define SCNo16 "ho"
#define SCNo32 "o"
#define SCNo64 __PRI64_PREFIX "o"

#define SCNoLEAST8 "hho"
#define SCNoLEAST16 "ho"
#define SCNoLEAST32 "o"
#define SCNoLEAST64 __PRI64_PREFIX "o"

#define SCNoFAST8 "hho"
#define SCNoFAST16 __PRIPTR_PREFIX "o"
#define SCNoFAST32 __PRIPTR_PREFIX "o"
#define SCNoFAST64 __PRI64_PREFIX "o"


#define SCNx8 "hhx"
#define SCNx16 "hx"
#define SCNx32 "x"
#define SCNx64 __PRI64_PREFIX "x"

#define SCNxLEAST8 "hhx"
#define SCNxLEAST16 "hx"
#define SCNxLEAST32 "x"
#define SCNxLEAST64 __PRI64_PREFIX "x"

#define SCNxFAST8 "hhx"
#define SCNxFAST16 __PRIPTR_PREFIX "x"
#define SCNxFAST32 __PRIPTR_PREFIX "x"
#define SCNxFAST64 __PRI64_PREFIX "x"



#define SCNdMAX __PRI64_PREFIX "d"
#define SCNiMAX __PRI64_PREFIX "i"
#define SCNoMAX __PRI64_PREFIX "o"
#define SCNuMAX __PRI64_PREFIX "u"
#define SCNxMAX __PRI64_PREFIX "x"


#define SCNdPTR __PRIPTR_PREFIX "d"
#define SCNiPTR __PRIPTR_PREFIX "i"
#define SCNoPTR __PRIPTR_PREFIX "o"
#define SCNuPTR __PRIPTR_PREFIX "u"
#define SCNxPTR __PRIPTR_PREFIX "x"









typedef struct
  {
    long int quot;
    long int rem;
  } imaxdiv_t;
# 297 "/usr/include/inttypes.h" 3 4
extern intmax_t imaxabs (intmax_t __n) __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__const__));


extern imaxdiv_t imaxdiv (intmax_t __numer, intmax_t __denom)
      __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__const__));


extern intmax_t strtoimax (const char *__restrict __nptr,
      char **__restrict __endptr, int __base) __attribute__ ((__nothrow__ , __leaf__));


extern uintmax_t strtoumax (const char *__restrict __nptr,
       char ** __restrict __endptr, int __base) __attribute__ ((__nothrow__ , __leaf__));


extern intmax_t wcstoimax (const __gwchar_t *__restrict __nptr,
      __gwchar_t **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__ , __leaf__));


extern uintmax_t wcstoumax (const __gwchar_t *__restrict __nptr,
       __gwchar_t ** __restrict __endptr, int __base)
     __attribute__ ((__nothrow__ , __leaf__));





extern long int __strtol_internal (const char *__restrict __nptr,
       char **__restrict __endptr,
       int __base, int __group)
  __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__nonnull__ (1))) __attribute__ ((__warn_unused_result__));

extern __inline __attribute__ ((__gnu_inline__)) intmax_t
__attribute__ ((__nothrow__ , __leaf__)) strtoimax (const char *__restrict nptr, char **__restrict endptr, int base)

{
  return __strtol_internal (nptr, endptr, base, 0);
}

extern unsigned long int __strtoul_internal (const char *__restrict __nptr,
          char ** __restrict __endptr,
          int __base, int __group)
  __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__nonnull__ (1))) __attribute__ ((__warn_unused_result__));

extern __inline __attribute__ ((__gnu_inline__)) uintmax_t
__attribute__ ((__nothrow__ , __leaf__)) strtoumax (const char *__restrict nptr, char **__restrict endptr, int base)

{
  return __strtoul_internal (nptr, endptr, base, 0);
}

extern long int __wcstol_internal (const __gwchar_t * __restrict __nptr,
       __gwchar_t **__restrict __endptr,
       int __base, int __group)
  __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__nonnull__ (1))) __attribute__ ((__warn_unused_result__));

extern __inline __attribute__ ((__gnu_inline__)) intmax_t
__attribute__ ((__nothrow__ , __leaf__)) wcstoimax (const __gwchar_t *__restrict nptr, __gwchar_t **__restrict endptr, int base)

{
  return __wcstol_internal (nptr, endptr, base, 0);
}

extern unsigned long int __wcstoul_internal (const __gwchar_t *
          __restrict __nptr,
          __gwchar_t **
          __restrict __endptr,
          int __base, int __group)
  __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__nonnull__ (1))) __attribute__ ((__warn_unused_result__));

extern __inline __attribute__ ((__gnu_inline__)) uintmax_t
__attribute__ ((__nothrow__ , __leaf__)) wcstoumax (const __gwchar_t *__restrict nptr, __gwchar_t **__restrict endptr, int base)

{
  return __wcstoul_internal (nptr, endptr, base, 0);
}
# 439 "/usr/include/inttypes.h" 3 4

# 145 "../gmp-impl.h" 2
# 158 "../gmp-impl.h"
#define WANT_TMP_DEBUG 0
# 184 "../gmp-impl.h"
#define alloca __builtin_alloca
# 210 "../gmp-impl.h"
#define BYTES_PER_MP_LIMB SIZEOF_MP_LIMB_T

#define GMP_LIMB_BYTES BYTES_PER_MP_LIMB




#define BITS_PER_ULONG (8 * SIZEOF_UNSIGNED_LONG)




typedef uint_least32_t gmp_uint_least32_t;
# 238 "../gmp-impl.h"
typedef intptr_t gmp_intptr_t;






typedef struct {mp_limb_t inv32;} gmp_pi1_t;
typedef struct {mp_limb_t inv21, inv32, inv53;} gmp_pi2_t;
# 256 "../gmp-impl.h"
#define ATTRIBUTE_CONST __attribute__ ((const))





#define ATTRIBUTE_NORETURN __attribute__ ((noreturn))







#define ATTRIBUTE_MALLOC __attribute__ ((malloc))
# 298 "../gmp-impl.h"
#define va_copy(dst,src) do { memcpy (&(dst), &(src), sizeof (va_list)); } while (0)
# 335 "../gmp-impl.h"
union tmp_align_t {
  mp_limb_t l;
  char *p;
};
#define __TMP_ALIGN sizeof (union tmp_align_t)







#define ROUND_UP_MULTIPLE(a,m) (POW2_P(m) ? (a) + (-(a))%(m) : (a)+(m)-1 - (((a)+(m)-1) % (m)))




struct tmp_reentrant_t {
  struct tmp_reentrant_t *next;
  size_t size;
};
 void *__gmp_tmp_reentrant_alloc (struct tmp_reentrant_t **, size_t) __attribute__ ((malloc));
 void __gmp_tmp_reentrant_free (struct tmp_reentrant_t *);



#define TMP_SDECL 
#define TMP_DECL struct tmp_reentrant_t *__tmp_marker
#define TMP_SMARK 
#define TMP_MARK __tmp_marker = 0
#define TMP_SALLOC(n) alloca(n)
#define TMP_BALLOC(n) __gmp_tmp_reentrant_alloc (&__tmp_marker, n)
#define TMP_ALLOC(n) (LIKELY ((n) < 65536) ? TMP_SALLOC(n) : TMP_BALLOC(n))

#define TMP_SFREE 
#define TMP_FREE do { if (UNLIKELY (__tmp_marker != 0)) __gmp_tmp_reentrant_free (__tmp_marker); } while (0)
# 472 "../gmp-impl.h"
#define TMP_ALLOC_TYPE(n,type) ((type *) TMP_ALLOC ((n) * sizeof (type)))
#define TMP_SALLOC_TYPE(n,type) ((type *) TMP_SALLOC ((n) * sizeof (type)))
#define TMP_BALLOC_TYPE(n,type) ((type *) TMP_BALLOC ((n) * sizeof (type)))
#define TMP_ALLOC_LIMBS(n) TMP_ALLOC_TYPE(n,mp_limb_t)
#define TMP_SALLOC_LIMBS(n) TMP_SALLOC_TYPE(n,mp_limb_t)
#define TMP_BALLOC_LIMBS(n) TMP_BALLOC_TYPE(n,mp_limb_t)
#define TMP_ALLOC_MP_PTRS(n) TMP_ALLOC_TYPE(n,mp_ptr)
#define TMP_SALLOC_MP_PTRS(n) TMP_SALLOC_TYPE(n,mp_ptr)
#define TMP_BALLOC_MP_PTRS(n) TMP_BALLOC_TYPE(n,mp_ptr)






#define TMP_ALLOC_LIMBS_2(xp,xsize,yp,ysize) do { if (WANT_TMP_DEBUG) { (xp) = TMP_ALLOC_LIMBS (xsize); (yp) = TMP_ALLOC_LIMBS (ysize); } else { (xp) = TMP_ALLOC_LIMBS ((xsize) + (ysize)); (yp) = (xp) + (xsize); } } while (0)
# 503 "../gmp-impl.h"
#define CRAY_Pragma(str) __GMP_CRAY_Pragma(str)
#define MPN_CMP(result,xp,yp,size) __GMPN_CMP(result, xp, yp, size)
#define LIKELY(cond) __GMP_LIKELY(cond)
#define UNLIKELY(cond) __GMP_UNLIKELY(cond)

#define ABS(x) ((x) >= 0 ? (x) : -(x))
#define ABS_CAST(T,x) ((x) >= 0 ? (T)(x) : -((T)((x) + 1) - 1))
#undef MIN
#define MIN(l,o) ((l) < (o) ? (l) : (o))
#undef MAX
#define MAX(h,i) ((h) > (i) ? (h) : (i))
#define numberof(x) (sizeof (x) / sizeof ((x)[0]))


#define SIZ(x) ((x)->_mp_size)
#define ABSIZ(x) ABS (SIZ (x))
#define PTR(x) ((x)->_mp_d)
#define EXP(x) ((x)->_mp_exp)
#define PREC(x) ((x)->_mp_prec)
#define ALLOC(x) ((x)->_mp_alloc)
#define NUM(x) mpq_numref(x)
#define DEN(x) mpq_denref(x)




#define POW2_P(n) (((n) & ((n) - 1)) == 0)



#define LOG2C(n) (((n) >= 0x1) + ((n) >= 0x2) + ((n) >= 0x4) + ((n) >= 0x8) + ((n) >= 0x10) + ((n) >= 0x20) + ((n) >= 0x40) + ((n) >= 0x80) + ((n) >= 0x100) + ((n) >= 0x200) + ((n) >= 0x400) + ((n) >= 0x800) + ((n) >= 0x1000) + ((n) >= 0x2000) + ((n) >= 0x4000) + ((n) >= 0x8000))
# 547 "../gmp-impl.h"
#define ULONG_MAX __GMP_ULONG_MAX


#define UINT_MAX __GMP_UINT_MAX


#define USHRT_MAX __GMP_USHRT_MAX

#define MP_LIMB_T_MAX (~ (mp_limb_t) 0)




#define ULONG_HIGHBIT (ULONG_MAX ^ ((unsigned long) ULONG_MAX >> 1))
#define UINT_HIGHBIT (UINT_MAX ^ ((unsigned) UINT_MAX >> 1))
#define USHRT_HIGHBIT ((unsigned short) (USHRT_MAX ^ ((unsigned short) USHRT_MAX >> 1)))
#define GMP_LIMB_HIGHBIT (MP_LIMB_T_MAX ^ (MP_LIMB_T_MAX >> 1))


#define LONG_MIN ((long) ULONG_HIGHBIT)


#define LONG_MAX (-(LONG_MIN+1))



#define INT_MIN ((int) UINT_HIGHBIT)


#define INT_MAX (-(INT_MIN+1))



#define SHRT_MIN ((short) USHRT_HIGHBIT)


#define SHRT_MAX ((short) (-(SHRT_MIN+1)))






#define MP_SIZE_T_MAX LONG_MAX
#define MP_SIZE_T_MIN LONG_MIN



#define MP_EXP_T_MAX MP_SIZE_T_MAX
#define MP_EXP_T_MIN MP_SIZE_T_MIN

#define LONG_HIGHBIT LONG_MIN
#define INT_HIGHBIT INT_MIN
#define SHRT_HIGHBIT SHRT_MIN


#define GMP_NUMB_HIGHBIT (CNST_LIMB(1) << (GMP_NUMB_BITS-1))


#define GMP_NAIL_LOWBIT CNST_LIMB(0)
# 641 "../gmp-impl.h"
#define MP_LIMB_T_SWAP(x,y) do { mp_limb_t __mp_limb_t_swap__tmp = (x); (x) = (y); (y) = __mp_limb_t_swap__tmp; } while (0)





#define MP_SIZE_T_SWAP(x,y) do { mp_size_t __mp_size_t_swap__tmp = (x); (x) = (y); (y) = __mp_size_t_swap__tmp; } while (0)






#define MP_PTR_SWAP(x,y) do { mp_ptr __mp_ptr_swap__tmp = (x); (x) = (y); (y) = __mp_ptr_swap__tmp; } while (0)





#define MP_SRCPTR_SWAP(x,y) do { mp_srcptr __mp_srcptr_swap__tmp = (x); (x) = (y); (y) = __mp_srcptr_swap__tmp; } while (0)






#define MPN_PTR_SWAP(xp,xs,yp,ys) do { MP_PTR_SWAP (xp, yp); MP_SIZE_T_SWAP (xs, ys); } while(0)




#define MPN_SRCPTR_SWAP(xp,xs,yp,ys) do { MP_SRCPTR_SWAP (xp, yp); MP_SIZE_T_SWAP (xs, ys); } while(0)





#define MPZ_PTR_SWAP(x,y) do { mpz_ptr __mpz_ptr_swap__tmp = (x); (x) = (y); (y) = __mpz_ptr_swap__tmp; } while (0)





#define MPZ_SRCPTR_SWAP(x,y) do { mpz_srcptr __mpz_srcptr_swap__tmp = (x); (x) = (y); (y) = __mpz_srcptr_swap__tmp; } while (0)
# 694 "../gmp-impl.h"
 extern void * (*__gmp_allocate_func) (size_t);
 extern void * (*__gmp_reallocate_func) (void *, size_t, size_t);
 extern void (*__gmp_free_func) (void *, size_t);

 void *__gmp_default_allocate (size_t);
 void *__gmp_default_reallocate (void *, size_t, size_t);
 void __gmp_default_free (void *, size_t);

#define __GMP_ALLOCATE_FUNC_TYPE(n,type) ((type *) (*__gmp_allocate_func) ((n) * sizeof (type)))

#define __GMP_ALLOCATE_FUNC_LIMBS(n) __GMP_ALLOCATE_FUNC_TYPE (n, mp_limb_t)

#define __GMP_REALLOCATE_FUNC_TYPE(p,old_size,new_size,type) ((type *) (*__gmp_reallocate_func) (p, (old_size) * sizeof (type), (new_size) * sizeof (type)))


#define __GMP_REALLOCATE_FUNC_LIMBS(p,old_size,new_size) __GMP_REALLOCATE_FUNC_TYPE(p, old_size, new_size, mp_limb_t)


#define __GMP_FREE_FUNC_TYPE(p,n,type) (*__gmp_free_func) (p, (n) * sizeof (type))
#define __GMP_FREE_FUNC_LIMBS(p,n) __GMP_FREE_FUNC_TYPE (p, n, mp_limb_t)

#define __GMP_REALLOCATE_FUNC_MAYBE(ptr,oldsize,newsize) do { if ((oldsize) != (newsize)) (ptr) = (*__gmp_reallocate_func) (ptr, oldsize, newsize); } while (0)





#define __GMP_REALLOCATE_FUNC_MAYBE_TYPE(ptr,oldsize,newsize,type) do { if ((oldsize) != (newsize)) (ptr) = (type *) (*__gmp_reallocate_func) (ptr, (oldsize) * sizeof (type), (newsize) * sizeof (type)); } while (0)
# 755 "../gmp-impl.h"
#define USE_LEADING_REGPARM 0
# 764 "../gmp-impl.h"
#define REGPARM_2_1(a,b,x) a,b,x
#define REGPARM_3_1(a,b,c,x) a,b,c,x
#define REGPARM_ATTR(n) 
# 780 "../gmp-impl.h"
#define ASM_L(name) LSYM_PREFIX "asm_%=_" #name
# 801 "../gmp-impl.h"
 void __gmpz_aorsmul_1 (mpz_ptr,mpz_srcptr,mp_limb_t,mp_size_t) ;
#define mpz_aorsmul_1(w,u,v,sub) __gmpz_aorsmul_1 (REGPARM_3_1 (w, u, v, sub))

#define mpz_n_pow_ui __gmpz_n_pow_ui
 void __gmpz_n_pow_ui (mpz_ptr, mp_srcptr, mp_size_t, unsigned long);


#define mpn_addmul_1c __MPN(addmul_1c)
 mp_limb_t __gmpn_addmul_1c (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t);


#define mpn_addmul_2 __MPN(addmul_2)
 mp_limb_t __gmpn_addmul_2 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);


#define mpn_addmul_3 __MPN(addmul_3)
 mp_limb_t __gmpn_addmul_3 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_addmul_4 __MPN(addmul_4)
 mp_limb_t __gmpn_addmul_4 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_addmul_5 __MPN(addmul_5)
 mp_limb_t __gmpn_addmul_5 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_addmul_6 __MPN(addmul_6)
 mp_limb_t __gmpn_addmul_6 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_addmul_7 __MPN(addmul_7)
 mp_limb_t __gmpn_addmul_7 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_addmul_8 __MPN(addmul_8)
 mp_limb_t __gmpn_addmul_8 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);


#define mpn_addmul_2s __MPN(addmul_2s)
 mp_limb_t __gmpn_addmul_2s (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);




#define mpn_addlsh1_n __MPN(addlsh1_n)
 mp_limb_t __gmpn_addlsh1_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_addlsh1_nc __MPN(addlsh1_nc)
 mp_limb_t __gmpn_addlsh1_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_addlsh1_n_ip1(dst,src,n) mpn_addlsh1_n(dst,dst,src,n)
#define HAVE_NATIVE_mpn_addlsh1_n_ip1 1
# 857 "../gmp-impl.h"
#define mpn_addlsh1_nc_ip1 __MPN(addlsh1_nc_ip1)
 mp_limb_t __gmpn_addlsh1_nc_ip1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);





#define mpn_addlsh2_n __MPN(addlsh2_n)
 mp_limb_t __gmpn_addlsh2_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_addlsh2_nc __MPN(addlsh2_nc)
 mp_limb_t __gmpn_addlsh2_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_addlsh2_n_ip1(dst,src,n) mpn_addlsh2_n(dst,dst,src,n)
#define HAVE_NATIVE_mpn_addlsh2_n_ip1 1
# 880 "../gmp-impl.h"
#define mpn_addlsh2_nc_ip1 __MPN(addlsh2_nc_ip1)
 mp_limb_t __gmpn_addlsh2_nc_ip1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);




#define mpn_addlsh_n __MPN(addlsh_n)
 mp_limb_t __gmpn_addlsh_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int);
#define mpn_addlsh_nc __MPN(addlsh_nc)
 mp_limb_t __gmpn_addlsh_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int, mp_limb_t);

#define mpn_addlsh_n_ip1(dst,src,n,s) mpn_addlsh_n(dst,dst,src,n,s)
#define HAVE_NATIVE_mpn_addlsh_n_ip1 1
# 901 "../gmp-impl.h"
#define mpn_addlsh_nc_ip1 __MPN(addlsh_nc_ip1)
 mp_limb_t __gmpn_addlsh_nc_ip1 (mp_ptr, mp_srcptr, mp_size_t, unsigned int, mp_limb_t);





#define mpn_sublsh1_n __MPN(sublsh1_n)
 mp_limb_t __gmpn_sublsh1_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_sublsh1_nc __MPN(sublsh1_nc)
 mp_limb_t __gmpn_sublsh1_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sublsh1_n_ip1(dst,src,n) mpn_sublsh1_n(dst,dst,src,n)
#define HAVE_NATIVE_mpn_sublsh1_n_ip1 1
# 924 "../gmp-impl.h"
#define mpn_sublsh1_nc_ip1 __MPN(sublsh1_nc_ip1)
 mp_limb_t __gmpn_sublsh1_nc_ip1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);




#define mpn_rsblsh1_n __MPN(rsblsh1_n)
 mp_limb_signed_t __gmpn_rsblsh1_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_rsblsh1_nc __MPN(rsblsh1_nc)
 mp_limb_signed_t __gmpn_rsblsh1_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);



#define mpn_sublsh2_n __MPN(sublsh2_n)
 mp_limb_t __gmpn_sublsh2_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_sublsh2_nc __MPN(sublsh2_nc)
 mp_limb_t __gmpn_sublsh2_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);




#define mpn_sublsh2_n_ip1 __MPN(sublsh2_n_ip1)
 mp_limb_t __gmpn_sublsh2_n_ip1 (mp_ptr, mp_srcptr, mp_size_t);





#define mpn_sublsh2_nc_ip1 __MPN(sublsh2_nc_ip1)
 mp_limb_t __gmpn_sublsh2_nc_ip1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);




#define mpn_sublsh_n __MPN(sublsh_n)
 mp_limb_t __gmpn_sublsh_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int);




#define mpn_sublsh_n_ip1 __MPN(sublsh_n_ip1)
 mp_limb_t __gmpn_sublsh_n_ip1 (mp_ptr, mp_srcptr, mp_size_t, unsigned int);





#define mpn_sublsh_nc_ip1 __MPN(sublsh_nc_ip1)
 mp_limb_t __gmpn_sublsh_nc_ip1 (mp_ptr, mp_srcptr, mp_size_t, unsigned int, mp_limb_t);




#define mpn_rsblsh2_n __MPN(rsblsh2_n)
 mp_limb_signed_t __gmpn_rsblsh2_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_rsblsh2_nc __MPN(rsblsh2_nc)
 mp_limb_signed_t __gmpn_rsblsh2_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);



#define mpn_rsblsh_n __MPN(rsblsh_n)
 mp_limb_signed_t __gmpn_rsblsh_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int);
#define mpn_rsblsh_nc __MPN(rsblsh_nc)
 mp_limb_signed_t __gmpn_rsblsh_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned int, mp_limb_t);



#define mpn_rsh1add_n __MPN(rsh1add_n)
 mp_limb_t __gmpn_rsh1add_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_rsh1add_nc __MPN(rsh1add_nc)
 mp_limb_t __gmpn_rsh1add_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);





#define mpn_rsh1sub_n __MPN(rsh1sub_n)
 mp_limb_t __gmpn_rsh1sub_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
#define mpn_rsh1sub_nc __MPN(rsh1sub_nc)
 mp_limb_t __gmpn_rsh1sub_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);


#define mpn_lshiftc __MPN(lshiftc)
 mp_limb_t __gmpn_lshiftc (mp_ptr, mp_srcptr, mp_size_t, unsigned int);


#define mpn_add_err1_n __MPN(add_err1_n)
 mp_limb_t __gmpn_add_err1_n (mp_ptr, mp_srcptr, mp_srcptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_add_err2_n __MPN(add_err2_n)
 mp_limb_t __gmpn_add_err2_n (mp_ptr, mp_srcptr, mp_srcptr, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_add_err3_n __MPN(add_err3_n)
 mp_limb_t __gmpn_add_err3_n (mp_ptr, mp_srcptr, mp_srcptr, mp_ptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sub_err1_n __MPN(sub_err1_n)
 mp_limb_t __gmpn_sub_err1_n (mp_ptr, mp_srcptr, mp_srcptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sub_err2_n __MPN(sub_err2_n)
 mp_limb_t __gmpn_sub_err2_n (mp_ptr, mp_srcptr, mp_srcptr, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sub_err3_n __MPN(sub_err3_n)
 mp_limb_t __gmpn_sub_err3_n (mp_ptr, mp_srcptr, mp_srcptr, mp_ptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_add_n_sub_n __MPN(add_n_sub_n)
 mp_limb_t __gmpn_add_n_sub_n (mp_ptr, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_add_n_sub_nc __MPN(add_n_sub_nc)
 mp_limb_t __gmpn_add_n_sub_nc (mp_ptr, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_addaddmul_1msb0 __MPN(addaddmul_1msb0)
 mp_limb_t __gmpn_addaddmul_1msb0 (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t);

#define mpn_divrem_1c __MPN(divrem_1c)
 mp_limb_t __gmpn_divrem_1c (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t);

#define mpn_dump __MPN(dump)
 void __gmpn_dump (mp_srcptr, mp_size_t);

#define mpn_fib2_ui __MPN(fib2_ui)
 mp_size_t __gmpn_fib2_ui (mp_ptr, mp_ptr, unsigned long);


#define __clz_tab __MPN(clz_tab)
#define mpn_udiv_w_sdiv __MPN(udiv_w_sdiv)

#define mpn_jacobi_base __MPN(jacobi_base)
 int __gmpn_jacobi_base (mp_limb_t, mp_limb_t, int) __attribute__ ((const));

#define mpn_jacobi_2 __MPN(jacobi_2)
 int __gmpn_jacobi_2 (mp_srcptr, mp_srcptr, unsigned);

#define mpn_jacobi_n __MPN(jacobi_n)
 int __gmpn_jacobi_n (mp_ptr, mp_ptr, mp_size_t, unsigned);

#define mpn_mod_1c __MPN(mod_1c)
 mp_limb_t __gmpn_mod_1c (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t) __attribute__ ((__pure__));

#define mpn_mul_1c __MPN(mul_1c)
 mp_limb_t __gmpn_mul_1c (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t);

#define mpn_mul_2 __MPN(mul_2)
 mp_limb_t __gmpn_mul_2 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_mul_3 __MPN(mul_3)
 mp_limb_t __gmpn_mul_3 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_mul_4 __MPN(mul_4)
 mp_limb_t __gmpn_mul_4 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_mul_5 __MPN(mul_5)
 mp_limb_t __gmpn_mul_5 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);

#define mpn_mul_6 __MPN(mul_6)
 mp_limb_t __gmpn_mul_6 (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);


#define mpn_mul_basecase __MPN(mul_basecase)
 void __gmpn_mul_basecase (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);


#define mpn_mullo_n __MPN(mullo_n)
 void __gmpn_mullo_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);


#define mpn_mullo_basecase __MPN(mullo_basecase)
 void __gmpn_mullo_basecase (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);


#define mpn_sqr __MPN(sqr)
 void __gmpn_sqr (mp_ptr, mp_srcptr, mp_size_t);


#define mpn_sqr_basecase __MPN(sqr_basecase)
 void __gmpn_sqr_basecase (mp_ptr, mp_srcptr, mp_size_t);


#define mpn_mulmid_basecase __MPN(mulmid_basecase)
 void __gmpn_mulmid_basecase (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_mulmid_n __MPN(mulmid_n)
 void __gmpn_mulmid_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_mulmid __MPN(mulmid)
 void __gmpn_mulmid (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_submul_1c __MPN(submul_1c)
 mp_limb_t __gmpn_submul_1c (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t);


#define mpn_redc_1 __MPN(redc_1)
 mp_limb_t __gmpn_redc_1 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);



#define mpn_redc_2 __MPN(redc_2)
 mp_limb_t __gmpn_redc_2 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);


#define mpn_redc_n __MPN(redc_n)
 void __gmpn_redc_n (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);



#define mpn_mod_1_1p_cps __MPN(mod_1_1p_cps)
 void __gmpn_mod_1_1p_cps (mp_limb_t [4], mp_limb_t);


#define mpn_mod_1_1p __MPN(mod_1_1p)
 mp_limb_t __gmpn_mod_1_1p (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [4]) __attribute__ ((__pure__));



#define mpn_mod_1s_2p_cps __MPN(mod_1s_2p_cps)
 void __gmpn_mod_1s_2p_cps (mp_limb_t [5], mp_limb_t);


#define mpn_mod_1s_2p __MPN(mod_1s_2p)
 mp_limb_t __gmpn_mod_1s_2p (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [5]) __attribute__ ((__pure__));



#define mpn_mod_1s_3p_cps __MPN(mod_1s_3p_cps)
 void __gmpn_mod_1s_3p_cps (mp_limb_t [6], mp_limb_t);


#define mpn_mod_1s_3p __MPN(mod_1s_3p)
 mp_limb_t __gmpn_mod_1s_3p (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [6]) __attribute__ ((__pure__));



#define mpn_mod_1s_4p_cps __MPN(mod_1s_4p_cps)
 void __gmpn_mod_1s_4p_cps (mp_limb_t [7], mp_limb_t);


#define mpn_mod_1s_4p __MPN(mod_1s_4p)
 mp_limb_t __gmpn_mod_1s_4p (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t [7]) __attribute__ ((__pure__));


#define mpn_bc_mulmod_bnm1 __MPN(bc_mulmod_bnm1)
 void __gmpn_bc_mulmod_bnm1 (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mulmod_bnm1 __MPN(mulmod_bnm1)
 void __gmpn_mulmod_bnm1 (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mulmod_bnm1_next_size __MPN(mulmod_bnm1_next_size)
 mp_size_t __gmpn_mulmod_bnm1_next_size (mp_size_t) __attribute__ ((const));
static inline mp_size_t
mpn_mulmod_bnm1_itch (mp_size_t rn, mp_size_t an, mp_size_t bn) {
  mp_size_t n, itch;
  n = rn >> 1;
  itch = rn + 4 +
    (an > n ? (bn > n ? rn : n) : 0);
  return itch;
}

#define mpn_sqrmod_bnm1 __MPN(sqrmod_bnm1)
 void __gmpn_sqrmod_bnm1 (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sqrmod_bnm1_next_size __MPN(sqrmod_bnm1_next_size)
 mp_size_t __gmpn_sqrmod_bnm1_next_size (mp_size_t) __attribute__ ((const));
static inline mp_size_t
mpn_sqrmod_bnm1_itch (mp_size_t rn, mp_size_t an) {
  mp_size_t n, itch;
  n = rn >> 1;
  itch = rn + 3 +
    (an > n ? an : 0);
  return itch;
}

typedef __gmp_randstate_struct *gmp_randstate_ptr;
typedef const __gmp_randstate_struct *gmp_randstate_srcptr;


typedef struct {
  void (*randseed_fn) (gmp_randstate_t, mpz_srcptr);
  void (*randget_fn) (gmp_randstate_t, mp_ptr, unsigned long int);
  void (*randclear_fn) (gmp_randstate_t);
  void (*randiset_fn) (gmp_randstate_ptr, gmp_randstate_srcptr);
} gmp_randfnptr_t;


#define RNG_FNPTR(rstate) ((rstate)->_mp_algdata._mp_lc)



#define RNG_STATE(rstate) ((rstate)->_mp_seed->_mp_d)


#define _gmp_rand(rp,state,bits) do { gmp_randstate_ptr __rstate = (state); (*((gmp_randfnptr_t *) RNG_FNPTR (__rstate))->randget_fn) (__rstate, rp, bits); } while (0)






 void __gmp_randinit_mt_noseed (gmp_randstate_t);
# 1232 "../gmp-impl.h"
 extern char __gmp_rands_initialized;
 extern gmp_randstate_t __gmp_rands;

#define RANDS ((__gmp_rands_initialized ? 0 : (__gmp_rands_initialized = 1, __gmp_randinit_mt_noseed (__gmp_rands), 0)), __gmp_rands)






#define RANDS_CLEAR() do { if (__gmp_rands_initialized) { __gmp_rands_initialized = 0; gmp_randclear (__gmp_rands); } } while (0)
# 1264 "../gmp-impl.h"
#define ABOVE_THRESHOLD(size,thresh) ((__builtin_constant_p (thresh) && (thresh) == 0) || (!(__builtin_constant_p (thresh) && (thresh) == MP_SIZE_T_MAX) && (size) >= (thresh)))




#define BELOW_THRESHOLD(size,thresh) (! ABOVE_THRESHOLD (size, thresh))

#define MPN_TOOM22_MUL_MINSIZE 4
#define MPN_TOOM2_SQR_MINSIZE 4

#define MPN_TOOM33_MUL_MINSIZE 17
#define MPN_TOOM3_SQR_MINSIZE 17

#define MPN_TOOM44_MUL_MINSIZE 30
#define MPN_TOOM4_SQR_MINSIZE 30

#define MPN_TOOM6H_MUL_MINSIZE 46
#define MPN_TOOM6_SQR_MINSIZE 46

#define MPN_TOOM8H_MUL_MINSIZE 86
#define MPN_TOOM8_SQR_MINSIZE 86

#define MPN_TOOM32_MUL_MINSIZE 10
#define MPN_TOOM42_MUL_MINSIZE 10
#define MPN_TOOM43_MUL_MINSIZE 25
#define MPN_TOOM53_MUL_MINSIZE 17
#define MPN_TOOM54_MUL_MINSIZE 31
#define MPN_TOOM63_MUL_MINSIZE 49

#define MPN_TOOM42_MULMID_MINSIZE 4

#define mpn_sqr_diagonal __MPN(sqr_diagonal)
 void __gmpn_sqr_diagonal (mp_ptr, mp_srcptr, mp_size_t);

#define mpn_sqr_diag_addlsh1 __MPN(sqr_diag_addlsh1)
 void __gmpn_sqr_diag_addlsh1 (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);

#define mpn_toom_interpolate_5pts __MPN(toom_interpolate_5pts)
 void __gmpn_toom_interpolate_5pts (mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_limb_t);

enum toom6_flags {toom6_all_pos = 0, toom6_vm1_neg = 1, toom6_vm2_neg = 2};
#define mpn_toom_interpolate_6pts __MPN(toom_interpolate_6pts)
 void __gmpn_toom_interpolate_6pts (mp_ptr, mp_size_t, enum toom6_flags, mp_ptr, mp_ptr, mp_ptr, mp_size_t);

enum toom7_flags { toom7_w1_neg = 1, toom7_w3_neg = 2 };
#define mpn_toom_interpolate_7pts __MPN(toom_interpolate_7pts)
 void __gmpn_toom_interpolate_7pts (mp_ptr, mp_size_t, enum toom7_flags, mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_ptr);

#define mpn_toom_interpolate_8pts __MPN(toom_interpolate_8pts)
 void __gmpn_toom_interpolate_8pts (mp_ptr, mp_size_t, mp_ptr, mp_ptr, mp_size_t, mp_ptr);

#define mpn_toom_interpolate_12pts __MPN(toom_interpolate_12pts)
 void __gmpn_toom_interpolate_12pts (mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_ptr);

#define mpn_toom_interpolate_16pts __MPN(toom_interpolate_16pts)
 void __gmpn_toom_interpolate_16pts (mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_ptr);

#define mpn_toom_couple_handling __MPN(toom_couple_handling)
 void __gmpn_toom_couple_handling (mp_ptr, mp_size_t, mp_ptr, int, mp_size_t, int, int);

#define mpn_toom_eval_dgr3_pm1 __MPN(toom_eval_dgr3_pm1)
 int __gmpn_toom_eval_dgr3_pm1 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);

#define mpn_toom_eval_dgr3_pm2 __MPN(toom_eval_dgr3_pm2)
 int __gmpn_toom_eval_dgr3_pm2 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);

#define mpn_toom_eval_pm1 __MPN(toom_eval_pm1)
 int __gmpn_toom_eval_pm1 (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);

#define mpn_toom_eval_pm2 __MPN(toom_eval_pm2)
 int __gmpn_toom_eval_pm2 (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);

#define mpn_toom_eval_pm2exp __MPN(toom_eval_pm2exp)
 int __gmpn_toom_eval_pm2exp (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr);

#define mpn_toom_eval_pm2rexp __MPN(toom_eval_pm2rexp)
 int __gmpn_toom_eval_pm2rexp (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr);

#define mpn_toom22_mul __MPN(toom22_mul)
 void __gmpn_toom22_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom32_mul __MPN(toom32_mul)
 void __gmpn_toom32_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom42_mul __MPN(toom42_mul)
 void __gmpn_toom42_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom52_mul __MPN(toom52_mul)
 void __gmpn_toom52_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom62_mul __MPN(toom62_mul)
 void __gmpn_toom62_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom2_sqr __MPN(toom2_sqr)
 void __gmpn_toom2_sqr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom33_mul __MPN(toom33_mul)
 void __gmpn_toom33_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom43_mul __MPN(toom43_mul)
 void __gmpn_toom43_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom53_mul __MPN(toom53_mul)
 void __gmpn_toom53_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom54_mul __MPN(toom54_mul)
 void __gmpn_toom54_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom63_mul __MPN(toom63_mul)
 void __gmpn_toom63_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom3_sqr __MPN(toom3_sqr)
 void __gmpn_toom3_sqr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom44_mul __MPN(toom44_mul)
 void __gmpn_toom44_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom4_sqr __MPN(toom4_sqr)
 void __gmpn_toom4_sqr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom6h_mul __MPN(toom6h_mul)
 void __gmpn_toom6h_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom6_sqr __MPN(toom6_sqr)
 void __gmpn_toom6_sqr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom8h_mul __MPN(toom8h_mul)
 void __gmpn_toom8h_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom8_sqr __MPN(toom8_sqr)
 void __gmpn_toom8_sqr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_toom42_mulmid __MPN(toom42_mulmid)
 void __gmpn_toom42_mulmid (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_fft_best_k __MPN(fft_best_k)
 int __gmpn_fft_best_k (mp_size_t, int) __attribute__ ((const));

#define mpn_mul_fft __MPN(mul_fft)
 mp_limb_t __gmpn_mul_fft (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, int);

#define mpn_mul_fft_full __MPN(mul_fft_full)
 void __gmpn_mul_fft_full (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_nussbaumer_mul __MPN(nussbaumer_mul)
 void __gmpn_nussbaumer_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);

#define mpn_fft_next_size __MPN(fft_next_size)
 mp_size_t __gmpn_fft_next_size (mp_size_t, int) __attribute__ ((const));

#define mpn_div_qr_2n_pi1 __MPN(div_qr_2n_pi1)
  mp_limb_t __gmpn_div_qr_2n_pi1 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, mp_limb_t);

#define mpn_div_qr_2u_pi1 __MPN(div_qr_2u_pi1)
  mp_limb_t __gmpn_div_qr_2u_pi1 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int, mp_limb_t);

#define mpn_sbpi1_div_qr __MPN(sbpi1_div_qr)
 mp_limb_t __gmpn_sbpi1_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sbpi1_div_q __MPN(sbpi1_div_q)
 mp_limb_t __gmpn_sbpi1_div_q (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sbpi1_divappr_q __MPN(sbpi1_divappr_q)
 mp_limb_t __gmpn_sbpi1_divappr_q (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_dcpi1_div_qr __MPN(dcpi1_div_qr)
 mp_limb_t __gmpn_dcpi1_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, gmp_pi1_t *);
#define mpn_dcpi1_div_qr_n __MPN(dcpi1_div_qr_n)
 mp_limb_t __gmpn_dcpi1_div_qr_n (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, gmp_pi1_t *, mp_ptr);

#define mpn_dcpi1_div_q __MPN(dcpi1_div_q)
 mp_limb_t __gmpn_dcpi1_div_q (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, gmp_pi1_t *);

#define mpn_dcpi1_divappr_q __MPN(dcpi1_divappr_q)
 mp_limb_t __gmpn_dcpi1_divappr_q (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, gmp_pi1_t *);
#define mpn_dcpi1_divappr_q_n __MPN(dcpi1_divappr_q_n)
 mp_limb_t __gmpn_dcpi1_divappr_q_n (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, gmp_pi1_t *, mp_ptr);

#define mpn_mu_div_qr __MPN(mu_div_qr)
 mp_limb_t __gmpn_mu_div_qr (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mu_div_qr_itch __MPN(mu_div_qr_itch)
 mp_size_t __gmpn_mu_div_qr_itch (mp_size_t, mp_size_t, int);
#define mpn_mu_div_qr_choose_in __MPN(mu_div_qr_choose_in)
 mp_size_t __gmpn_mu_div_qr_choose_in (mp_size_t, mp_size_t, int);

#define mpn_preinv_mu_div_qr __MPN(preinv_mu_div_qr)
 mp_limb_t __gmpn_preinv_mu_div_qr (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_preinv_mu_div_qr_itch __MPN(preinv_mu_div_qr_itch)
 mp_size_t __gmpn_preinv_mu_div_qr_itch (mp_size_t, mp_size_t, mp_size_t);

#define mpn_mu_divappr_q __MPN(mu_divappr_q)
 mp_limb_t __gmpn_mu_divappr_q (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mu_divappr_q_itch __MPN(mu_divappr_q_itch)
 mp_size_t __gmpn_mu_divappr_q_itch (mp_size_t, mp_size_t, int);
#define mpn_mu_divappr_q_choose_in __MPN(mu_divappr_q_choose_in)
 mp_size_t __gmpn_mu_divappr_q_choose_in (mp_size_t, mp_size_t, int);

#define mpn_preinv_mu_divappr_q __MPN(preinv_mu_divappr_q)
 mp_limb_t __gmpn_preinv_mu_divappr_q (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_mu_div_q __MPN(mu_div_q)
 mp_limb_t __gmpn_mu_div_q (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mu_div_q_itch __MPN(mu_div_q_itch)
 mp_size_t __gmpn_mu_div_q_itch (mp_size_t, mp_size_t, int);

#define mpn_div_q __MPN(div_q)
 void __gmpn_div_q (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);

#define mpn_invert __MPN(invert)
 void __gmpn_invert (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_invert_itch(n) mpn_invertappr_itch(n)

#define mpn_ni_invertappr __MPN(ni_invertappr)
 mp_limb_t __gmpn_ni_invertappr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_invertappr __MPN(invertappr)
 mp_limb_t __gmpn_invertappr (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_invertappr_itch(n) (3 * (n) + 2)

#define mpn_binvert __MPN(binvert)
 void __gmpn_binvert (mp_ptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_binvert_itch __MPN(binvert_itch)
 mp_size_t __gmpn_binvert_itch (mp_size_t);

#define mpn_bdiv_q_1 __MPN(bdiv_q_1)
 mp_limb_t __gmpn_bdiv_q_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_pi1_bdiv_q_1 __MPN(pi1_bdiv_q_1)
 mp_limb_t __gmpn_pi1_bdiv_q_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int);

#define mpn_sbpi1_bdiv_qr __MPN(sbpi1_bdiv_qr)
 mp_limb_t __gmpn_sbpi1_bdiv_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sbpi1_bdiv_q __MPN(sbpi1_bdiv_q)
 void __gmpn_sbpi1_bdiv_q (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_dcpi1_bdiv_qr __MPN(dcpi1_bdiv_qr)
 mp_limb_t __gmpn_dcpi1_bdiv_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);
#define mpn_dcpi1_bdiv_qr_n_itch __MPN(dcpi1_bdiv_qr_n_itch)
 mp_size_t __gmpn_dcpi1_bdiv_qr_n_itch (mp_size_t);

#define mpn_dcpi1_bdiv_qr_n __MPN(dcpi1_bdiv_qr_n)
 mp_limb_t __gmpn_dcpi1_bdiv_qr_n (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);
#define mpn_dcpi1_bdiv_q __MPN(dcpi1_bdiv_q)
 void __gmpn_dcpi1_bdiv_q (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_dcpi1_bdiv_q_n_itch __MPN(dcpi1_bdiv_q_n_itch)
 mp_size_t __gmpn_dcpi1_bdiv_q_n_itch (mp_size_t);
#define mpn_dcpi1_bdiv_q_n __MPN(dcpi1_bdiv_q_n)
 void __gmpn_dcpi1_bdiv_q_n (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);

#define mpn_mu_bdiv_qr __MPN(mu_bdiv_qr)
 mp_limb_t __gmpn_mu_bdiv_qr (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mu_bdiv_qr_itch __MPN(mu_bdiv_qr_itch)
 mp_size_t __gmpn_mu_bdiv_qr_itch (mp_size_t, mp_size_t);

#define mpn_mu_bdiv_q __MPN(mu_bdiv_q)
 void __gmpn_mu_bdiv_q (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_mu_bdiv_q_itch __MPN(mu_bdiv_q_itch)
 mp_size_t __gmpn_mu_bdiv_q_itch (mp_size_t, mp_size_t);

#define mpn_bdiv_qr __MPN(bdiv_qr)
 mp_limb_t __gmpn_bdiv_qr (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_bdiv_qr_itch __MPN(bdiv_qr_itch)
 mp_size_t __gmpn_bdiv_qr_itch (mp_size_t, mp_size_t);

#define mpn_bdiv_q __MPN(bdiv_q)
 void __gmpn_bdiv_q (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_bdiv_q_itch __MPN(bdiv_q_itch)
 mp_size_t __gmpn_bdiv_q_itch (mp_size_t, mp_size_t);

#define mpn_divexact __MPN(divexact)
 void __gmpn_divexact (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);
#define mpn_divexact_itch __MPN(divexact_itch)
 mp_size_t __gmpn_divexact_itch (mp_size_t, mp_size_t);


#define mpn_bdiv_dbm1c __MPN(bdiv_dbm1c)
 mp_limb_t __gmpn_bdiv_dbm1c (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t);


#define mpn_bdiv_dbm1(dst,src,size,divisor) mpn_bdiv_dbm1c (dst, src, size, divisor, __GMP_CAST (mp_limb_t, 0))


#define mpn_powm __MPN(powm)
 void __gmpn_powm (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_powlo __MPN(powlo)
 void __gmpn_powlo (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
#define mpn_powm_sec __MPN(powm_sec)
 void __gmpn_powm_sec (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_powm_sec_itch __MPN(powm_sec_itch)
 mp_size_t __gmpn_powm_sec_itch (mp_size_t, mp_size_t, mp_size_t);
#define mpn_tabselect __MPN(tabselect)
 void __gmpn_tabselect (volatile mp_limb_t *, volatile mp_limb_t *, mp_size_t, mp_size_t, mp_size_t);
#define mpn_addcnd_n __MPN(addcnd_n)
 mp_limb_t __gmpn_addcnd_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);
#define mpn_subcnd_n __MPN(subcnd_n)
 mp_limb_t __gmpn_subcnd_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_sb_div_qr_sec __MPN(sb_div_qr_sec)
 void __gmpn_sb_div_qr_sec (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sbpi1_div_qr_sec __MPN(sbpi1_div_qr_sec)
 mp_limb_t __gmpn_sbpi1_div_qr_sec (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);
#define mpn_sb_div_r_sec __MPN(sb_div_r_sec)
 void __gmpn_sb_div_r_sec (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sbpi1_div_r_sec __MPN(sbpi1_div_r_sec)
 void __gmpn_sbpi1_div_r_sec (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);




#define DIVEXACT_BY3_METHOD 0






#undef mpn_divexact_by3
#define mpn_divexact_by3(dst,src,size) (3 & mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 3)))
# 1593 "../gmp-impl.h"
#define mpn_divexact_by5(dst,src,size) (7 & 3 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 5)))
# 1618 "../gmp-impl.h"
#define mpn_divexact_by15(dst,src,size) (15 & 1 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 15)))



#define mpz_divexact_gcd __gmpz_divexact_gcd
 void __gmpz_divexact_gcd (mpz_ptr, mpz_srcptr, mpz_srcptr);

#define mpz_prodlimbs __gmpz_prodlimbs
 mp_size_t __gmpz_prodlimbs (mpz_ptr, mp_ptr, mp_size_t);

#define mpz_oddfac_1 __gmpz_oddfac_1
 void __gmpz_oddfac_1 (mpz_ptr, mp_limb_t, unsigned);

#define mpz_inp_str_nowhite __gmpz_inp_str_nowhite




#define mpn_divisible_p __MPN(divisible_p)
 int __gmpn_divisible_p (mp_srcptr, mp_size_t, mp_srcptr, mp_size_t) __attribute__ ((__pure__));

#define mpn_rootrem __MPN(rootrem)
 mp_size_t __gmpn_rootrem (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_broot __MPN(broot)
 void __gmpn_broot (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_broot_invm1 __MPN(broot_invm1)
 void __gmpn_broot_invm1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);

#define mpn_brootinv __MPN(brootinv)
 void __gmpn_brootinv (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);

#define mpn_bsqrt __MPN(bsqrt)
 void __gmpn_bsqrt (mp_ptr, mp_srcptr, mp_bitcnt_t, mp_ptr);

#define mpn_bsqrtinv __MPN(bsqrtinv)
 int __gmpn_bsqrtinv (mp_ptr, mp_srcptr, mp_bitcnt_t, mp_ptr);
# 1674 "../gmp-impl.h"
#define MPN_COPY_INCR(dst,src,size) do { ASSERT ((size) >= 0); ASSERT (MPN_SAME_OR_INCR_P (dst, src, size)); mpn_copyi (dst, src, size); } while (0)
# 1727 "../gmp-impl.h"
#define MPN_COPY_DECR(dst,src,size) do { ASSERT ((size) >= 0); ASSERT (MPN_SAME_OR_DECR_P (dst, src, size)); mpn_copyd (dst, src, size); } while (0)
# 1764 "../gmp-impl.h"
#define MPN_COPY(d,s,n) do { ASSERT (MPN_SAME_OR_SEPARATE_P (d, s, n)); MPN_COPY_INCR (d, s, n); } while (0)
# 1773 "../gmp-impl.h"
#define MPN_REVERSE(dst,src,size) do { mp_ptr __dst = (dst); mp_size_t __size = (size); mp_srcptr __src = (src) + __size - 1; mp_size_t __i; ASSERT ((size) >= 0); ASSERT (! MPN_OVERLAP_P (dst, size, src, size)); CRAY_Pragma ("_CRI ivdep"); for (__i = 0; __i < __size; __i++) { *__dst = *__src; __dst++; __src--; } } while (0)
# 1826 "../gmp-impl.h"
#define MPN_ZERO(dst,n) do { ASSERT ((n) >= 0); if ((n) != 0) { mp_ptr __dst = (dst); mp_size_t __n = (n); do *__dst++ = 0; while (--__n); } } while (0)
# 1854 "../gmp-impl.h"
#define MPN_NORMALIZE(DST,NLIMBS) do { while ((NLIMBS) > 0) { if ((DST)[(NLIMBS) - 1] != 0) break; (NLIMBS)--; } } while (0)
# 1865 "../gmp-impl.h"
#define MPN_NORMALIZE_NOT_ZERO(DST,NLIMBS) do { while (1) { ASSERT ((NLIMBS) >= 1); if ((DST)[(NLIMBS) - 1] != 0) break; (NLIMBS)--; } } while (0)
# 1881 "../gmp-impl.h"
#define MPN_STRIP_LOW_ZEROS_NOT_ZERO(ptr,size,low) do { ASSERT ((size) >= 1); ASSERT ((low) == (ptr)[0]); while ((low) == 0) { (size)--; ASSERT ((size) >= 1); (ptr)++; (low) = *(ptr); } } while (0)
# 1899 "../gmp-impl.h"
#define MPZ_TMP_INIT(X,NLIMBS) do { mpz_ptr __x = (X); ASSERT ((NLIMBS) >= 1); __x->_mp_alloc = (NLIMBS); __x->_mp_d = TMP_ALLOC_LIMBS (NLIMBS); } while (0)
# 1917 "../gmp-impl.h"
#define _mpz_newalloc _mpz_realloc


#define MPZ_REALLOC(z,n) (UNLIKELY ((n) > ALLOC(z)) ? (mp_ptr) _mpz_realloc(z,n) : PTR(z))


#define MPZ_NEWALLOC(z,n) (UNLIKELY ((n) > ALLOC(z)) ? (mp_ptr) _mpz_newalloc(z,n) : PTR(z))



#define MPZ_EQUAL_1_P(z) (SIZ(z)==1 && PTR(z)[0] == 1)
# 1950 "../gmp-impl.h"
#define MPN_FIB2_SIZE(n) ((mp_size_t) ((n) / 32 * 23 / GMP_NUMB_BITS) + 4)
# 1960 "../gmp-impl.h"
 extern const mp_limb_t __gmp_fib_table[];
#define FIB_TABLE(n) (__gmp_fib_table[(n)+1])

extern const mp_limb_t __gmp_oddfac_table[];
extern const mp_limb_t __gmp_odd2fac_table[];
extern const unsigned char __gmp_fac2cnt_table[];
extern const mp_limb_t __gmp_limbroots_table[];


static inline unsigned
log_n_max (mp_limb_t n)
{
  unsigned log;
  for (log = 8; n > __gmp_limbroots_table[log - 1]; log--);
  return log;
}

#define SIEVESIZE 512
typedef struct
{
  unsigned long d;
  unsigned long s0;
  unsigned long sqrt_s0;
  unsigned char s[512 + 1];
} gmp_primesieve_t;

#define gmp_init_primesieve __gmp_init_primesieve
 void __gmp_init_primesieve (gmp_primesieve_t *);

#define gmp_nextprime __gmp_nextprime
 unsigned long int __gmp_nextprime (gmp_primesieve_t *);

#define gmp_primesieve __gmp_primesieve
 mp_limb_t __gmp_primesieve (mp_ptr, mp_limb_t);
# 2049 "../gmp-impl.h"
#define MUL_TOOM22_THRESHOLD_LIMIT MUL_TOOM22_THRESHOLD


#define MUL_TOOM33_THRESHOLD_LIMIT MUL_TOOM33_THRESHOLD


#define MULLO_BASECASE_THRESHOLD_LIMIT MULLO_BASECASE_THRESHOLD
# 2086 "../gmp-impl.h"
#define SQR_TOOM3_THRESHOLD_LIMIT SQR_TOOM3_THRESHOLD
# 2110 "../gmp-impl.h"
#define DIVEXACT_JEB_THRESHOLD 25
# 2158 "../gmp-impl.h"
#define MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD (INV_MULMOD_BNM1_THRESHOLD/2)
# 2182 "../gmp-impl.h"
#define FFT_FIRST_K 4
# 2208 "../gmp-impl.h"
#define MUL_FFT_TABLE { MUL_TOOM33_THRESHOLD * 4, MUL_TOOM33_THRESHOLD * 8, MUL_TOOM33_THRESHOLD * 16, MUL_TOOM33_THRESHOLD * 32, MUL_TOOM33_THRESHOLD * 96, MUL_TOOM33_THRESHOLD * 288, 0 }
# 2218 "../gmp-impl.h"
#define SQR_FFT_TABLE { SQR_TOOM3_THRESHOLD * 4, SQR_TOOM3_THRESHOLD * 8, SQR_TOOM3_THRESHOLD * 16, SQR_TOOM3_THRESHOLD * 32, SQR_TOOM3_THRESHOLD * 96, SQR_TOOM3_THRESHOLD * 288, 0 }
# 2228 "../gmp-impl.h"
struct fft_table_nk
{
  unsigned int n:27;
  unsigned int k:5;
};


#define FFT_TABLE_ATTRS static const


#define MPN_FFT_TABLE_SIZE 16







#define GET_STR_DC_THRESHOLD 18



#define GET_STR_PRECOMPUTE_THRESHOLD 35



#define SET_STR_DC_THRESHOLD 750



#define SET_STR_PRECOMPUTE_THRESHOLD 2000



#define FAC_ODD_THRESHOLD 35



#define FAC_DSC_THRESHOLD 400





#define MPN_OVERLAP_P(xp,xsize,yp,ysize) ((xp) + (xsize) > (yp) && (yp) + (ysize) > (xp))

#define MEM_OVERLAP_P(xp,xsize,yp,ysize) ( (char *) (xp) + (xsize) > (char *) (yp) && (char *) (yp) + (ysize) > (char *) (xp))





#define MPN_SAME_OR_SEPARATE_P(xp,yp,size) MPN_SAME_OR_SEPARATE2_P(xp, size, yp, size)

#define MPN_SAME_OR_SEPARATE2_P(xp,xsize,yp,ysize) ((xp) == (yp) || ! MPN_OVERLAP_P (xp, xsize, yp, ysize))





#define MPN_SAME_OR_INCR2_P(dst,dsize,src,ssize) ((dst) <= (src) || ! MPN_OVERLAP_P (dst, dsize, src, ssize))

#define MPN_SAME_OR_INCR_P(dst,src,size) MPN_SAME_OR_INCR2_P(dst, size, src, size)

#define MPN_SAME_OR_DECR2_P(dst,dsize,src,ssize) ((dst) >= (src) || ! MPN_OVERLAP_P (dst, dsize, src, ssize))

#define MPN_SAME_OR_DECR_P(dst,src,size) MPN_SAME_OR_DECR2_P(dst, size, src, size)
# 2308 "../gmp-impl.h"
#define ASSERT_LINE __LINE__





#define ASSERT_FILE __FILE__




 void __gmp_assert_header (const char *, int);
 void __gmp_assert_fail (const char *, int, const char *) __attribute__ ((noreturn));


#define ASSERT_FAIL(expr) __gmp_assert_fail (ASSERT_FILE, ASSERT_LINE, #expr)




#define ASSERT_ALWAYS(expr) do { if (UNLIKELY (!(expr))) ASSERT_FAIL (expr); } while (0)
# 2337 "../gmp-impl.h"
#define ASSERT(expr) do {} while (0)
# 2351 "../gmp-impl.h"
#define ASSERT_CARRY(expr) (expr)
#define ASSERT_NOCARRY(expr) (expr)
# 2361 "../gmp-impl.h"
#define ASSERT_CODE(expr) 
# 2388 "../gmp-impl.h"
#define ASSERT_MPQ_CANONICAL(q) do {} while (0)



#define ASSERT_ALWAYS_LIMB(limb) do { mp_limb_t __nail = (limb) & GMP_NAIL_MASK; ASSERT_ALWAYS (__nail == 0); } while (0)




#define ASSERT_ALWAYS_MPN(ptr,size) do { if (GMP_NAIL_BITS != 0) { mp_size_t __i; for (__i = 0; __i < (size); __i++) ASSERT_ALWAYS_LIMB ((ptr)[__i]); } } while (0)
# 2411 "../gmp-impl.h"
#define ASSERT_LIMB(limb) do {} while (0)
#define ASSERT_MPN(ptr,size) do {} while (0)
# 2440 "../gmp-impl.h"
#define ASSERT_MPN_ZERO_P(ptr,size) do {} while (0)
#define ASSERT_MPN_NONZERO_P(ptr,size) do {} while (0)
# 2460 "../gmp-impl.h"
#define MPN_LOGOPS_N_INLINE(rp,up,vp,n,operation) do { mp_srcptr __up = (up); mp_srcptr __vp = (vp); mp_ptr __rp = (rp); mp_size_t __n = (n); mp_limb_t __a, __b; ASSERT (__n > 0); ASSERT (MPN_SAME_OR_SEPARATE_P (__rp, __up, __n)); ASSERT (MPN_SAME_OR_SEPARATE_P (__rp, __vp, __n)); __up += __n; __vp += __n; __rp += __n; __n = -__n; do { __a = __up[__n]; __b = __vp[__n]; __rp[__n] = operation; } while (++__n); } while (0)
# 2530 "../gmp-impl.h"
#define mpn_trialdiv __MPN(trialdiv)
 mp_limb_t __gmpn_trialdiv (mp_srcptr, mp_size_t, mp_size_t, int *);

#define mpn_remove __MPN(remove)
 mp_bitcnt_t __gmpn_remove (mp_ptr, mp_size_t *, mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_bitcnt_t);




#define ADDC_LIMB(cout,w,x,y) do { mp_limb_t __x = (x); mp_limb_t __y = (y); mp_limb_t __w = __x + __y; (w) = __w; (cout) = __w < __x; } while (0)
# 2562 "../gmp-impl.h"
#define SUBC_LIMB(cout,w,x,y) do { mp_limb_t __x = (x); mp_limb_t __y = (y); mp_limb_t __w = __x - __y; (w) = __w; (cout) = __w > __x; } while (0)
# 2601 "../gmp-impl.h"
#define MPN_IORD_U(ptr,incr,aors) do { mp_ptr __ptr_dummy; if (__builtin_constant_p (incr) && (incr) == 0) { } else if (__builtin_constant_p (incr) && (incr) == 1) { __asm__ __volatile__ ("\n" ASM_L(top) ":\n" "\t" aors "\t$1, (%0)\n" "\tlea\t%c2(%0), %0\n" "\tjc\t" ASM_L(top) : "=r" (__ptr_dummy) : "0" (ptr), "n" (sizeof(mp_limb_t)) : "memory"); } else { __asm__ __volatile__ ( aors "\t%2, (%0)\n" "\tjnc\t" ASM_L(done) "\n" ASM_L(top) ":\n" "\t" aors "\t$1, %c3(%0)\n" "\tlea\t%c3(%0), %0\n" "\tjc\t" ASM_L(top) "\n" ASM_L(done) ":\n" : "=r" (__ptr_dummy) : "0" (ptr), "ri" ((mp_limb_t) (incr)), "n" (sizeof(mp_limb_t)) : "memory"); } } while (0)
# 2640 "../gmp-impl.h"
#define MPN_INCR_U(ptr,size,incr) MPN_IORD_U (ptr, incr, "addq")
#define MPN_DECR_U(ptr,size,incr) MPN_IORD_U (ptr, incr, "subq")

#define mpn_incr_u(ptr,incr) MPN_INCR_U (ptr, 0, incr)
#define mpn_decr_u(ptr,incr) MPN_DECR_U (ptr, 0, incr)
# 2779 "../gmp-impl.h"
struct bases
{



  int chars_per_limb;


  mp_limb_t logb2;


  mp_limb_t log2b;




  mp_limb_t big_base;




  mp_limb_t big_base_inverted;
};

#define mp_bases __MPN(bases)
 extern const struct bases __gmpn_bases[257];





#define DIGITS_IN_BASE_FROM_BITS(res,nbits,b) do { mp_limb_t _ph, _dummy; size_t _nbits = (nbits); umul_ppmm (_ph, _dummy, mp_bases[b].logb2, _nbits); _ph += (_dummy + _nbits < _dummy); res = _ph + 1; } while (0)







#define DIGITS_IN_BASEGT2_FROM_BITS(res,nbits,b) do { mp_limb_t _ph, _dummy; size_t _nbits = (nbits); umul_ppmm (_ph, _dummy, mp_bases[b].logb2 + 1, _nbits); res = _ph + 1; } while (0)
# 2835 "../gmp-impl.h"
#define MPN_SIZEINBASE(result,ptr,size,base) do { int __lb_base, __cnt; size_t __totbits; ASSERT ((size) >= 0); ASSERT ((base) >= 2); ASSERT ((base) < numberof (mp_bases)); if ((size) == 0) (result) = 1; else { count_leading_zeros (__cnt, (ptr)[(size)-1]); __totbits = (size_t) (size) * GMP_NUMB_BITS - (__cnt - GMP_NAIL_BITS); if (POW2_P (base)) { __lb_base = mp_bases[base].big_base; (result) = (__totbits + __lb_base - 1) / __lb_base; } else { DIGITS_IN_BASEGT2_FROM_BITS (result, __totbits, base); } } } while (0)
# 2865 "../gmp-impl.h"
#define MPN_SIZEINBASE_2EXP(result,ptr,size,base2exp) do { int __cnt; mp_bitcnt_t __totbits; ASSERT ((size) > 0); ASSERT ((ptr)[(size)-1] != 0); count_leading_zeros (__cnt, (ptr)[(size)-1]); __totbits = (mp_bitcnt_t) (size) * GMP_NUMB_BITS - (__cnt - GMP_NAIL_BITS); (result) = (__totbits + (base2exp)-1) / (base2exp); } while (0)
# 2878 "../gmp-impl.h"
#define BITS_TO_LIMBS(n) (((n) + (GMP_NUMB_BITS - 1)) / GMP_NUMB_BITS)






#define LIMBS_PER_ULONG 1
#define MPN_SET_UI(zp,zn,u) (zp)[0] = (u); (zn) = ((zp)[0] != 0);


#define MPZ_FAKE_UI(z,zp,u) (zp)[0] = (u); PTR (z) = (zp); SIZ (z) = ((zp)[0] != 0); ASSERT_CODE (ALLOC (z) = 1);
# 2915 "../gmp-impl.h"
#define TARGET_REGISTER_STARVED 0
# 2932 "../gmp-impl.h"
#define LIMB_HIGHBIT_TO_MASK(n) (((mp_limb_signed_t) -1 >> 1) < 0 ? (mp_limb_signed_t) (n) >> (GMP_LIMB_BITS - 1) : (n) & GMP_LIMB_HIGHBIT ? MP_LIMB_T_MAX : CNST_LIMB(0))






#define mpn_invert_limb __MPN(invert_limb)
 mp_limb_t __gmpn_invert_limb (mp_limb_t) __attribute__ ((const));

#define invert_limb(invxl,xl) do { (invxl) = mpn_invert_limb (xl); } while (0)
# 2957 "../gmp-impl.h"
#define invert_pi1(dinv,d1,d0) do { mp_limb_t _v, _p, _t1, _t0, _mask; invert_limb (_v, d1); _p = (d1) * _v; _p += (d0); if (_p < (d0)) { _v--; _mask = -(mp_limb_t) (_p >= (d1)); _p -= (d1); _v += _mask; _p -= _mask & (d1); } umul_ppmm (_t1, _t0, d0, _v); _p += _t1; if (_p < _t1) { _v--; if (UNLIKELY (_p >= (d1))) { if (_p > (d1) || _t0 >= (d0)) _v--; } } (dinv).inv32 = _v; } while (0)
# 3007 "../gmp-impl.h"
#define udiv_qrnnd_preinv(q,r,nh,nl,d,di) do { mp_limb_t _qh, _ql, _r, _mask; umul_ppmm (_qh, _ql, (nh), (di)); if (__builtin_constant_p (nl) && (nl) == 0) { _qh += (nh) + 1; _r = - _qh * (d); _mask = -(mp_limb_t) (_r > _ql); _qh += _mask; _r += _mask & (d); } else { add_ssaaaa (_qh, _ql, _qh, _ql, (nh) + 1, (nl)); _r = (nl) - _qh * (d); _mask = -(mp_limb_t) (_r > _ql); _qh += _mask; _r += _mask & (d); if (UNLIKELY (_r >= (d))) { _r -= (d); _qh++; } } (r) = _r; (q) = _qh; } while (0)
# 3039 "../gmp-impl.h"
#define udiv_rnnd_preinv(r,nh,nl,d,di) do { mp_limb_t _qh, _ql, _r, _mask; umul_ppmm (_qh, _ql, (nh), (di)); if (__builtin_constant_p (nl) && (nl) == 0) { _r = ~(_qh + (nh)) * (d); _mask = -(mp_limb_t) (_r > _ql); _r += _mask & (d); } else { add_ssaaaa (_qh, _ql, _qh, _ql, (nh) + 1, (nl)); _r = (nl) - _qh * (d); _mask = -(mp_limb_t) (_r > _ql); _r += _mask & (d); if (UNLIKELY (_r >= (d))) _r -= (d); } (r) = _r; } while (0)
# 3069 "../gmp-impl.h"
#define udiv_qr_3by2(q,r1,r0,n2,n1,n0,d1,d0,dinv) do { mp_limb_t _q0, _t1, _t0, _mask; umul_ppmm ((q), _q0, (n2), (dinv)); add_ssaaaa ((q), _q0, (q), _q0, (n2), (n1)); (r1) = (n1) - (d1) * (q); sub_ddmmss ((r1), (r0), (r1), (n0), (d1), (d0)); umul_ppmm (_t1, _t0, (d0), (q)); sub_ddmmss ((r1), (r0), (r1), (r0), _t1, _t0); (q)++; _mask = - (mp_limb_t) ((r1) >= _q0); (q) += _mask; add_ssaaaa ((r1), (r0), (r1), (r0), _mask & (d1), _mask & (d0)); if (UNLIKELY ((r1) >= (d1))) { if ((r1) > (d1) || (r0) >= (d0)) { (q)++; sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0)); } } } while (0)
# 3097 "../gmp-impl.h"
#define mpn_preinv_divrem_1 __MPN(preinv_divrem_1)
 mp_limb_t __gmpn_preinv_divrem_1 (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int);
# 3110 "../gmp-impl.h"
#define MPN_DIVREM_OR_PREINV_DIVREM_1(qp,xsize,ap,size,d,dinv,shift) mpn_preinv_divrem_1 (qp, xsize, ap, size, d, dinv, shift)
# 3123 "../gmp-impl.h"
#define MPN_MOD_OR_PREINV_MOD_1(src,size,divisor,inverse) (BELOW_THRESHOLD (size, PREINV_MOD_1_TO_MOD_1_THRESHOLD) ? mpn_preinv_mod_1 (src, size, divisor, inverse) : mpn_mod_1 (src, size, divisor))






#define mpn_mod_34lsub1 __MPN(mod_34lsub1)
 mp_limb_t __gmpn_mod_34lsub1 (mp_srcptr, mp_size_t) __attribute__ ((__pure__));
# 3148 "../gmp-impl.h"
#define mpn_divexact_1 __MPN(divexact_1)
 void __gmpn_divexact_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t);


#define MPN_DIVREM_OR_DIVEXACT_1(rp,up,n,d) do { if (BELOW_THRESHOLD (n, DIVEXACT_1_THRESHOLD)) ASSERT_NOCARRY (mpn_divrem_1 (rp, (mp_size_t) 0, up, n, d)); else { ASSERT (mpn_mod_1 (up, n, d) == 0); mpn_divexact_1 (rp, up, n, d); } } while (0)
# 3164 "../gmp-impl.h"
#define mpn_modexact_1c_odd __MPN(modexact_1c_odd)
 mp_limb_t __gmpn_modexact_1c_odd (mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t) __attribute__ ((__pure__));



#define mpn_modexact_1_odd __MPN(modexact_1_odd)
 mp_limb_t __gmpn_modexact_1_odd (mp_srcptr, mp_size_t, mp_limb_t) __attribute__ ((__pure__));





#define MPN_MOD_OR_MODEXACT_1_ODD(src,size,divisor) (BELOW_THRESHOLD (size, BMOD_1_TO_MOD_1_THRESHOLD) ? mpn_modexact_1_odd (src, size, divisor) : mpn_mod_1 (src, size, divisor))
# 3201 "../gmp-impl.h"
#define binvert_limb_table __gmp_binvert_limb_table
 extern const unsigned char __gmp_binvert_limb_table[128];

#define binvert_limb(inv,n) do { mp_limb_t __n = (n); mp_limb_t __inv; ASSERT ((__n & 1) == 1); __inv = binvert_limb_table[(__n/2) & 0x7F]; if (GMP_NUMB_BITS > 8) __inv = 2 * __inv - __inv * __inv * __n; if (GMP_NUMB_BITS > 16) __inv = 2 * __inv - __inv * __inv * __n; if (GMP_NUMB_BITS > 32) __inv = 2 * __inv - __inv * __inv * __n; if (GMP_NUMB_BITS > 64) { int __invbits = 64; do { __inv = 2 * __inv - __inv * __inv * __n; __invbits *= 2; } while (__invbits < GMP_NUMB_BITS); } ASSERT ((__inv * __n & GMP_NUMB_MASK) == 1); (inv) = __inv & GMP_NUMB_MASK; } while (0)
# 3227 "../gmp-impl.h"
#define modlimb_invert binvert_limb





#define MODLIMB_INVERSE_3 (((GMP_NUMB_MAX >> (GMP_NUMB_BITS % 2)) / 3) * 2 + 1)



#define GMP_NUMB_CEIL_MAX_DIV3 (GMP_NUMB_MAX / 3 + 1)
#define GMP_NUMB_CEIL_2MAX_DIV3 ((GMP_NUMB_MAX>>1) / 3 + 1 + GMP_NUMB_HIGHBIT)
# 3247 "../gmp-impl.h"
#define NEG_MOD(r,a,d) do { ASSERT ((d) != 0); ASSERT_LIMB (a); ASSERT_LIMB (d); if ((a) <= (d)) { (r) = (d) - (a); } else { unsigned __twos; mp_limb_t __dnorm; count_leading_zeros (__twos, d); __twos -= GMP_NAIL_BITS; __dnorm = (d) << __twos; (r) = ((a) <= __dnorm ? __dnorm : 2*__dnorm) - (a); } ASSERT_LIMB (r); } while (0)
# 3272 "../gmp-impl.h"
#define LOW_ZEROS_MASK(n) (((n) & -(n)) - 1)
# 3332 "../gmp-impl.h"
#define ULONG_PARITY(p,n) do { unsigned long __n = (n); int __p = 0; do { __p ^= 0x96696996L >> (__n & 0x1F); __n >>= 5; } while (__n != 0); (p) = __p & 1; } while (0)
# 3382 "../gmp-impl.h"
#define BSWAP_LIMB(dst,src) do { __asm__ ("bswap %q0" : "=r" (dst) : "0" (src)); } while (0)
# 3484 "../gmp-impl.h"
#define BSWAP_LIMB_FETCH(limb,src) BSWAP_LIMB (limb, *(src))
# 3508 "../gmp-impl.h"
#define BSWAP_LIMB_STORE(dst,limb) BSWAP_LIMB (*(dst), limb)




#define MPN_BSWAP(dst,src,size) do { mp_ptr __dst = (dst); mp_srcptr __src = (src); mp_size_t __size = (size); mp_size_t __i; ASSERT ((size) >= 0); ASSERT (MPN_SAME_OR_SEPARATE_P (dst, src, size)); CRAY_Pragma ("_CRI ivdep"); for (__i = 0; __i < __size; __i++) { BSWAP_LIMB_FETCH (*__dst, __src); __dst++; __src++; } } while (0)
# 3531 "../gmp-impl.h"
#define MPN_BSWAP_REVERSE(dst,src,size) do { mp_ptr __dst = (dst); mp_size_t __size = (size); mp_srcptr __src = (src) + __size - 1; mp_size_t __i; ASSERT ((size) >= 0); ASSERT (! MPN_OVERLAP_P (dst, size, src, size)); CRAY_Pragma ("_CRI ivdep"); for (__i = 0; __i < __size; __i++) { BSWAP_LIMB_FETCH (*__dst, __src); __dst++; __src--; } } while (0)
# 3630 "../gmp-impl.h"
#define popc_limb(result,input) do { mp_limb_t __x = (input); __x -= (__x >> 1) & MP_LIMB_T_MAX/3; __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5); __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17; __x = ((__x >> 8) + __x); __x = ((__x >> 16) + __x); __x = ((__x >> 32) + __x); (result) = __x & 0xff; } while (0)
# 3646 "../gmp-impl.h"
typedef unsigned int UQItype __attribute__ ((mode (QI)));
typedef int SItype __attribute__ ((mode (SI)));
typedef unsigned int USItype __attribute__ ((mode (SI)));
typedef int DItype __attribute__ ((mode (DI)));
typedef unsigned int UDItype __attribute__ ((mode (DI)));
# 3664 "../gmp-impl.h"
typedef mp_limb_t UWtype;
typedef unsigned int UHWtype;
#define W_TYPE_SIZE GMP_LIMB_BITS
# 3696 "../gmp-impl.h"
#define _GMP_IEEE_FLOATS 1
union ieee_double_extract
{
  struct
    {
      gmp_uint_least32_t manl:32;
      gmp_uint_least32_t manh:20;
      gmp_uint_least32_t exp:11;
      gmp_uint_least32_t sig:1;
    } s;
  double d;
};
# 3743 "../gmp-impl.h"
#define MP_BASE_AS_DOUBLE (4.0 * ((mp_limb_t) 1 << (GMP_NUMB_BITS - 2)))


#define LIMBS_PER_DOUBLE ((53 + GMP_NUMB_BITS - 2) / GMP_NUMB_BITS + 1)

 int __gmp_extract_double (mp_ptr, double);

#define mpn_get_d __gmpn_get_d
 double __gmpn_get_d (mp_srcptr, mp_size_t, mp_size_t, long) __attribute__ ((__pure__));







#define DOUBLE_NAN_INF_ACTION(x,a_nan,a_inf) do { union ieee_double_extract u; u.d = (x); if (UNLIKELY (u.s.exp == 0x7FF)) { if (u.s.manl == 0 && u.s.manh == 0) { a_inf; } else { a_nan; } } } while (0)
# 3813 "../gmp-impl.h"
#define FORCE_DOUBLE(d) do { volatile double __gmp_force = (d); (d) = __gmp_force; } while (0)






 extern const unsigned char __gmp_digit_value_tab[];

 extern int __gmp_junk;
 extern const int __gmp_0;
 void __gmp_exception (int) __attribute__ ((noreturn));
 void __gmp_divide_by_zero (void) __attribute__ ((noreturn));
 void __gmp_sqrt_of_negative (void) __attribute__ ((noreturn));
 void __gmp_invalid_operation (void) __attribute__ ((noreturn));
#define GMP_ERROR(code) __gmp_exception (code)
#define DIVIDE_BY_ZERO __gmp_divide_by_zero ()
#define SQRT_OF_NEGATIVE __gmp_sqrt_of_negative ()




#define CNST_LIMB(C) ((mp_limb_t) C ##L)
# 3861 "../gmp-impl.h"
#define PP CNST_LIMB(0xE221F97C30E94E1D)
#define PP_INVERTED CNST_LIMB(0x21CFE6CFC938B36B)
#define PP_FIRST_OMITTED 59
# 3881 "../gmp-impl.h"
#define JACOBI_S0(a) (((a) == 1) | ((a) == -1))


#define JACOBI_U0(a) ((a) == 1)






#define JACOBI_LS0(alow,asize) (((asize) == 1 || (asize) == -1) && (alow) == 1)




#define JACOBI_Z0(a) JACOBI_LS0 (PTR(a)[0], SIZ(a))


#define JACOBI_0U(b) ((b) == 1)


#define JACOBI_0S(b) ((b) == 1 || (b) == -1)


#define JACOBI_0LS(blow,bsize) (((bsize) == 1 || (bsize) == -1) && (blow) == 1)



#define JACOBI_BIT1_TO_PN(result_bit1) (1 - ((int) (result_bit1) & 2))





#define JACOBI_TWO_U_BIT1(b) ((int) (((b) >> 1) ^ (b)))



#define JACOBI_TWOS_U_BIT1(twos,b) ((int) ((twos) << 1) & JACOBI_TWO_U_BIT1 (b))



#define JACOBI_TWOS_U(twos,b) (JACOBI_BIT1_TO_PN (JACOBI_TWOS_U_BIT1 (twos, b)))




#define JACOBI_N1B_BIT1(b) ((int) (b))




#define JACOBI_ASGN_SU_BIT1(a,b) ((((a) < 0) << 1) & JACOBI_N1B_BIT1(b))




#define JACOBI_BSGN_SS_BIT1(a,b) ((((a)<0) & ((b)<0)) << 1)




#define JACOBI_BSGN_SZ_BIT1(a,b) JACOBI_BSGN_SS_BIT1 (a, SIZ(b))




#define JACOBI_BSGN_ZS_BIT1(a,b) JACOBI_BSGN_SZ_BIT1 (b, a)







#define JACOBI_RECIP_UU_BIT1(a,b) ((int) ((a) & (b)))






#define JACOBI_STRIP_LOW_ZEROS(result_bit1,a,b_ptr,b_size,b_low) do { ASSERT ((b_size) >= 1); ASSERT ((b_low) == (b_ptr)[0]); while (UNLIKELY ((b_low) == 0)) { (b_size)--; ASSERT ((b_size) >= 1); (b_ptr)++; (b_low) = *(b_ptr); ASSERT (((a) & 1) != 0); if ((GMP_NUMB_BITS % 2) == 1) (result_bit1) ^= JACOBI_TWO_U_BIT1(a); } } while (0)
# 3995 "../gmp-impl.h"
#define JACOBI_MOD_OR_MODEXACT_1_ODD(result_bit1,a_rem,a_ptr,a_size,b) do { mp_srcptr __a_ptr = (a_ptr); mp_size_t __a_size = (a_size); mp_limb_t __b = (b); ASSERT (__a_size >= 1); ASSERT (__b & 1); if ((GMP_NUMB_BITS % 2) != 0 || ABOVE_THRESHOLD (__a_size, BMOD_1_TO_MOD_1_THRESHOLD)) { (a_rem) = mpn_mod_1 (__a_ptr, __a_size, __b); } else { (result_bit1) ^= JACOBI_N1B_BIT1 (__b); (a_rem) = mpn_modexact_1_odd (__a_ptr, __a_size, __b); } } while (0)
# 4017 "../gmp-impl.h"
#define jacobi_table __gmp_jacobi_table
 extern const unsigned char __gmp_jacobi_table[208];
# 4028 "../gmp-impl.h"
static inline unsigned
mpn_jacobi_init (unsigned a, unsigned b, unsigned s)
{
  do {} while (0);
  do {} while (0);
  return ((a & 3) << 2) + (b & 2) + s;
}

static inline int
mpn_jacobi_finish (unsigned bits)
{

  do {} while (0);

  return 1-2*(bits & 1);
}

static inline unsigned
mpn_jacobi_update (unsigned bits, unsigned denominator, unsigned q)
{







  do {} while (0);
  do {} while (0);
  do {} while (0);
# 4077 "../gmp-impl.h"
  return bits = __gmp_jacobi_table[(bits << 3) + (denominator << 2) + q];
}


#define mpn_matrix22_mul __MPN(matrix22_mul)
 void __gmpn_matrix22_mul (mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_matrix22_mul_strassen __MPN(matrix22_mul_strassen)
 void __gmpn_matrix22_mul_strassen (mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_matrix22_mul_itch __MPN(matrix22_mul_itch)
 mp_size_t __gmpn_matrix22_mul_itch (mp_size_t, mp_size_t);
# 4108 "../gmp-impl.h"
#define MPN_EXTRACT_NUMB(count,xh,xl) ((((xh) << ((count) - GMP_NAIL_BITS)) & GMP_NUMB_MASK) | ((xl) >> (GMP_LIMB_BITS - (count))))
# 4118 "../gmp-impl.h"
struct hgcd_matrix1
{
  mp_limb_t u[2][2];
};

#define mpn_hgcd2 __MPN (hgcd2)
 int __gmpn_hgcd2 (mp_limb_t, mp_limb_t, mp_limb_t, mp_limb_t, struct hgcd_matrix1 *);

#define mpn_hgcd_mul_matrix1_vector __MPN (hgcd_mul_matrix1_vector)
 mp_size_t __gmpn_hgcd_mul_matrix1_vector (const struct hgcd_matrix1 *, mp_ptr, mp_srcptr, mp_ptr, mp_size_t);

#define mpn_matrix22_mul1_inverse_vector __MPN (matrix22_mul1_inverse_vector)
 mp_size_t __gmpn_matrix22_mul1_inverse_vector (const struct hgcd_matrix1 *, mp_ptr, mp_srcptr, mp_ptr, mp_size_t);

#define mpn_hgcd2_jacobi __MPN (hgcd2_jacobi)
 int __gmpn_hgcd2_jacobi (mp_limb_t, mp_limb_t, mp_limb_t, mp_limb_t, struct hgcd_matrix1 *, unsigned *);

struct hgcd_matrix
{
  mp_size_t alloc;
  mp_size_t n;
  mp_ptr p[2][2];
};

#define MPN_HGCD_MATRIX_INIT_ITCH(n) (4 * ((n+1)/2 + 1))

#define mpn_hgcd_matrix_init __MPN (hgcd_matrix_init)
 void __gmpn_hgcd_matrix_init (struct hgcd_matrix *, mp_size_t, mp_ptr);

#define mpn_hgcd_matrix_update_q __MPN (hgcd_matrix_update_q)
 void __gmpn_hgcd_matrix_update_q (struct hgcd_matrix *, mp_srcptr, mp_size_t, unsigned, mp_ptr);

#define mpn_hgcd_matrix_mul_1 __MPN (hgcd_matrix_mul_1)
 void __gmpn_hgcd_matrix_mul_1 (struct hgcd_matrix *, const struct hgcd_matrix1 *, mp_ptr);

#define mpn_hgcd_matrix_mul __MPN (hgcd_matrix_mul)
 void __gmpn_hgcd_matrix_mul (struct hgcd_matrix *, const struct hgcd_matrix *, mp_ptr);

#define mpn_hgcd_matrix_adjust __MPN (hgcd_matrix_adjust)
 mp_size_t __gmpn_hgcd_matrix_adjust (const struct hgcd_matrix *, mp_size_t, mp_ptr, mp_ptr, mp_size_t, mp_ptr);

#define mpn_hgcd_step __MPN(hgcd_step)
 mp_size_t __gmpn_hgcd_step (mp_size_t, mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr);

#define mpn_hgcd_reduce __MPN(hgcd_reduce)
 mp_size_t __gmpn_hgcd_reduce (struct hgcd_matrix *, mp_ptr, mp_ptr, mp_size_t, mp_size_t, mp_ptr);

#define mpn_hgcd_reduce_itch __MPN(hgcd_reduce_itch)
 mp_size_t __gmpn_hgcd_reduce_itch (mp_size_t, mp_size_t);

#define mpn_hgcd_itch __MPN (hgcd_itch)
 mp_size_t __gmpn_hgcd_itch (mp_size_t);

#define mpn_hgcd __MPN (hgcd)
 mp_size_t __gmpn_hgcd (mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr);

#define mpn_hgcd_appr_itch __MPN (hgcd_appr_itch)
 mp_size_t __gmpn_hgcd_appr_itch (mp_size_t);

#define mpn_hgcd_appr __MPN (hgcd_appr)
 int __gmpn_hgcd_appr (mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr);

#define mpn_hgcd_jacobi __MPN (hgcd_jacobi)
 mp_size_t __gmpn_hgcd_jacobi (mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, unsigned *, mp_ptr);

typedef void gcd_subdiv_step_hook(void *, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, int);


#define MPN_GCD_SUBDIV_STEP_ITCH(n) (n)

#define mpn_gcd_subdiv_step __MPN(gcd_subdiv_step)
 mp_size_t __gmpn_gcd_subdiv_step (mp_ptr, mp_ptr, mp_size_t, mp_size_t, gcd_subdiv_step_hook *, void *, mp_ptr);

struct gcdext_ctx
{

  mp_ptr gp;
  mp_size_t gn;
  mp_ptr up;
  mp_size_t *usize;


  mp_size_t un;
  mp_ptr u0, u1, tp;
};

#define mpn_gcdext_hook __MPN (gcdext_hook)
gcd_subdiv_step_hook __gmpn_gcdext_hook;

#define MPN_GCDEXT_LEHMER_N_ITCH(n) (4*(n) + 3)

#define mpn_gcdext_lehmer_n __MPN(gcdext_lehmer_n)
 mp_size_t __gmpn_gcdext_lehmer_n (mp_ptr, mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr);


#define MPN_GCDEXT_LEHMER_ITCH(an,bn) (5*(an) + 4*(bn) + 8)






#define HGCD_APPR_THRESHOLD 400



#define HGCD_REDUCE_THRESHOLD 1000



#define GCD_DC_THRESHOLD 1000



#define GCDEXT_DC_THRESHOLD 600



struct powers
{
  mp_ptr p;
  mp_size_t n;
  mp_size_t shift;
  size_t digits_in_base;
  int base;
};
typedef struct powers powers_t;
#define mpn_dc_set_str_powtab_alloc(n) ((n) + GMP_LIMB_BITS)
#define mpn_dc_set_str_itch(n) ((n) + GMP_LIMB_BITS)
#define mpn_dc_get_str_powtab_alloc(n) ((n) + 2 * GMP_LIMB_BITS)
#define mpn_dc_get_str_itch(n) ((n) + GMP_LIMB_BITS)

#define mpn_dc_set_str __MPN(dc_set_str)
 mp_size_t __gmpn_dc_set_str (mp_ptr, const unsigned char *, size_t, const powers_t *, mp_ptr);
#define mpn_bc_set_str __MPN(bc_set_str)
 mp_size_t __gmpn_bc_set_str (mp_ptr, const unsigned char *, size_t, int);
#define mpn_set_str_compute_powtab __MPN(set_str_compute_powtab)
 void __gmpn_set_str_compute_powtab (powers_t *, mp_ptr, mp_size_t, int);






#define __GMPF_BITS_TO_PREC(n) ((mp_size_t) ((__GMP_MAX (53, n) + 2 * GMP_NUMB_BITS - 1) / GMP_NUMB_BITS))

#define __GMPF_PREC_TO_BITS(n) ((mp_bitcnt_t) (n) * GMP_NUMB_BITS - GMP_NUMB_BITS)


 extern mp_size_t __gmp_default_fp_limb_precision;



#define DIGITS_IN_BASE_PER_LIMB(res,nlimbs,b) do { mp_limb_t _ph, _pl; umul_ppmm (_ph, _pl, mp_bases[b].logb2, GMP_NUMB_BITS * (mp_limb_t) (nlimbs)); res = _ph; } while (0)
# 4281 "../gmp-impl.h"
#define LIMBS_PER_DIGIT_IN_BASE(res,ndigits,b) do { mp_limb_t _ph, _dummy; umul_ppmm (_ph, _dummy, mp_bases[b].log2b, (mp_limb_t) (ndigits)); res = 8 * _ph / GMP_NUMB_BITS + 2; } while (0)
# 4301 "../gmp-impl.h"
#define MPF_SIGNIFICANT_DIGITS(n,base,prec) do { size_t rawn; ASSERT (base >= 2 && base < numberof (mp_bases)); DIGITS_IN_BASE_PER_LIMB (rawn, (prec) - 1, base); n = rawn + 2; } while (0)
# 4328 "../gmp-impl.h"
#define GMP_DECIMAL_POINT (localeconv()->decimal_point)






#define DOPRNT_CONV_FIXED 1
#define DOPRNT_CONV_SCIENTIFIC 2
#define DOPRNT_CONV_GENERAL 3

#define DOPRNT_JUSTIFY_NONE 0
#define DOPRNT_JUSTIFY_LEFT 1
#define DOPRNT_JUSTIFY_RIGHT 2
#define DOPRNT_JUSTIFY_INTERNAL 3

#define DOPRNT_SHOWBASE_YES 1
#define DOPRNT_SHOWBASE_NO 2
#define DOPRNT_SHOWBASE_NONZERO 3

struct doprnt_params_t {
  int base;
  int conv;
  const char *expfmt;
  int exptimes4;
  char fill;
  int justify;
  int prec;
  int showbase;
  int showpoint;
  int showtrailing;
  char sign;
  int width;
};
# 4478 "../gmp-impl.h"
typedef int (*gmp_doscan_scan_t) (void *, const char *, ...);
typedef void *(*gmp_doscan_step_t) (void *, int);
typedef int (*gmp_doscan_get_t) (void *);
typedef int (*gmp_doscan_unget_t) (int, void *);

struct gmp_doscan_funs_t {
  gmp_doscan_scan_t scan;
  gmp_doscan_step_t step;
  gmp_doscan_get_t get;
  gmp_doscan_unget_t unget;
};
extern const struct gmp_doscan_funs_t __gmp_fscanf_funs;
extern const struct gmp_doscan_funs_t __gmp_sscanf_funs;







#define MPZ_CHECK_FORMAT(z) do { ASSERT_ALWAYS (SIZ(z) == 0 || PTR(z)[ABSIZ(z) - 1] != 0); ASSERT_ALWAYS (ALLOC(z) >= ABSIZ(z)); ASSERT_ALWAYS_MPN (PTR(z), ABSIZ(z)); } while (0)






#define MPQ_CHECK_FORMAT(q) do { MPZ_CHECK_FORMAT (mpq_numref (q)); MPZ_CHECK_FORMAT (mpq_denref (q)); ASSERT_ALWAYS (SIZ(mpq_denref(q)) >= 1); if (SIZ(mpq_numref(q)) == 0) { ASSERT_ALWAYS (SIZ(mpq_denref(q)) == 1 && PTR(mpq_denref(q))[0] == 1); } else { mpz_t g; mpz_init (g); mpz_gcd (g, mpq_numref(q), mpq_denref(q)); ASSERT_ALWAYS (mpz_cmp_ui (g, 1) == 0); mpz_clear (g); } } while (0)
# 4528 "../gmp-impl.h"
#define MPF_CHECK_FORMAT(f) do { ASSERT_ALWAYS (PREC(f) >= __GMPF_BITS_TO_PREC(53)); ASSERT_ALWAYS (ABSIZ(f) <= PREC(f)+1); if (SIZ(f) == 0) ASSERT_ALWAYS (EXP(f) == 0); if (SIZ(f) != 0) ASSERT_ALWAYS (PTR(f)[ABSIZ(f) - 1] != 0); } while (0)
# 4539 "../gmp-impl.h"
#define MPZ_PROVOKE_REALLOC(z) do { ALLOC(z) = ABSIZ(z); } while (0)
# 4598 "../gmp-impl.h"
 void __gmpn_cpuvec_init (void);



#define CPUVEC_THRESHOLD(field) ((LIKELY (__gmpn_cpuvec_initialized) ? 0 : (__gmpn_cpuvec_init (), 0)), __gmpn_cpuvec.field)





#define mpn_add_nc __MPN(add_nc)
 mp_limb_t __gmpn_add_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);
# 4623 "../gmp-impl.h"
#define mpn_sub_nc __MPN(sub_nc)
 mp_limb_t __gmpn_sub_nc (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);
# 4636 "../gmp-impl.h"
static inline int
mpn_zero_p (mp_srcptr ap, mp_size_t n)
{
  mp_size_t i;
  for (i = n - 1; i >= 0; i--)
    {
      if (ap[i] != 0)
 return 0;
    }
  return 1;
}
# 4986 "../gmp-impl.h"
#define mpn_toom22_mul_itch(an,bn) (2 * ((an) + GMP_NUMB_BITS))

#define mpn_toom2_sqr_itch(an) (2 * ((an) + GMP_NUMB_BITS))





#define mpn_toom33_mul_itch(an,bn) (3 * (an) + GMP_NUMB_BITS)

#define mpn_toom3_sqr_itch(an) (3 * (an) + GMP_NUMB_BITS)





#define mpn_toom44_mul_itch(an,bn) (3 * (an) + GMP_NUMB_BITS)

#define mpn_toom4_sqr_itch(an) (3 * (an) + GMP_NUMB_BITS)


#define mpn_toom6_sqr_itch(n) (((n) - SQR_TOOM6_THRESHOLD)*2 + MAX(SQR_TOOM6_THRESHOLD*2 + GMP_NUMB_BITS*6, mpn_toom4_sqr_itch(SQR_TOOM6_THRESHOLD)))




#define MUL_TOOM6H_MIN ((MUL_TOOM6H_THRESHOLD > MUL_TOOM44_THRESHOLD) ? MUL_TOOM6H_THRESHOLD : MUL_TOOM44_THRESHOLD)


#define mpn_toom6_mul_n_itch(n) (((n) - MUL_TOOM6H_MIN)*2 + MAX(MUL_TOOM6H_MIN*2 + GMP_NUMB_BITS*6, mpn_toom44_mul_itch(MUL_TOOM6H_MIN,MUL_TOOM6H_MIN)))




static inline mp_size_t
mpn_toom6h_mul_itch (mp_size_t an, mp_size_t bn) {
  mp_size_t estimatedN;
  estimatedN = (an + bn) / (size_t) 10 + 1;
  return (((estimatedN * 6) - ((298 > 178) ? 298 : 178))*2 + ((((298 > 178) ? 298 : 178)*2 + (64 - 0)*6) > ((3 * (((298 > 178) ? 298 : 178)) + (64 - 0))) ? (((298 > 178) ? 298 : 178)*2 + (64 - 0)*6) : ((3 * (((298 > 178) ? 298 : 178)) + (64 - 0)))));
}

#define mpn_toom8_sqr_itch(n) ((((n)*15)>>3) - ((SQR_TOOM8_THRESHOLD*15)>>3) + MAX(((SQR_TOOM8_THRESHOLD*15)>>3) + GMP_NUMB_BITS*6, mpn_toom6_sqr_itch(SQR_TOOM8_THRESHOLD)))




#define MUL_TOOM8H_MIN ((MUL_TOOM8H_THRESHOLD > MUL_TOOM6H_MIN) ? MUL_TOOM8H_THRESHOLD : MUL_TOOM6H_MIN)


#define mpn_toom8_mul_n_itch(n) ((((n)*15)>>3) - ((MUL_TOOM8H_MIN*15)>>3) + MAX(((MUL_TOOM8H_MIN*15)>>3) + GMP_NUMB_BITS*6, mpn_toom6_mul_n_itch(MUL_TOOM8H_MIN)))




static inline mp_size_t
mpn_toom8h_mul_itch (mp_size_t an, mp_size_t bn) {
  mp_size_t estimatedN;
  estimatedN = (an + bn) / (size_t) 14 + 1;
  return ((((estimatedN * 8)*15)>>3) - ((((357 > ((298 > 178) ? 298 : 178)) ? 357 : ((298 > 178) ? 298 : 178))*15)>>3) + ((((((357 > ((298 > 178) ? 298 : 178)) ? 357 : ((298 > 178) ? 298 : 178))*15)>>3) + (64 - 0)*6) > ((((((357 > ((298 > 178) ? 298 : 178)) ? 357 : ((298 > 178) ? 298 : 178))) - ((298 > 178) ? 298 : 178))*2 + ((((298 > 178) ? 298 : 178)*2 + (64 - 0)*6) > ((3 * (((298 > 178) ? 298 : 178)) + (64 - 0))) ? (((298 > 178) ? 298 : 178)*2 + (64 - 0)*6) : ((3 * (((298 > 178) ? 298 : 178)) + (64 - 0)))))) ? (((((357 > ((298 > 178) ? 298 : 178)) ? 357 : ((298 > 178) ? 298 : 178))*15)>>3) + (64 - 0)*6) : ((((((357 > ((298 > 178) ? 298 : 178)) ? 357 : ((298 > 178) ? 298 : 178))) - ((298 > 178) ? 298 : 178))*2 + ((((298 > 178) ? 298 : 178)*2 + (64 - 0)*6) > ((3 * (((298 > 178) ? 298 : 178)) + (64 - 0))) ? (((298 > 178) ? 298 : 178)*2 + (64 - 0)*6) : ((3 * (((298 > 178) ? 298 : 178)) + (64 - 0))))))));
}

static inline mp_size_t
mpn_toom32_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (2 * an >= 3 * bn ? (an - 1) / (size_t) 3 : (bn - 1) >> 1);
  mp_size_t itch = 2 * n + 1;

  return itch;
}

static inline mp_size_t
mpn_toom42_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = an >= 2 * bn ? (an + 3) >> 2 : (bn + 1) >> 1;
  return 6 * n + 3;
}

static inline mp_size_t
mpn_toom43_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (3 * an >= 4 * bn ? (an - 1) >> 2 : (bn - 1) / (size_t) 3);

  return 6*n + 4;
}

static inline mp_size_t
mpn_toom52_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (2 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) >> 1);
  return 6*n + 4;
}

static inline mp_size_t
mpn_toom53_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (3 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) / (size_t) 3);
  return 10 * n + 10;
}

static inline mp_size_t
mpn_toom62_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (an >= 3 * bn ? (an - 1) / (size_t) 6 : (bn - 1) >> 1);
  return 10 * n + 10;
}

static inline mp_size_t
mpn_toom63_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (an >= 2 * bn ? (an - 1) / (size_t) 6 : (bn - 1) / (size_t) 3);
  return 9 * n + 3;
}

static inline mp_size_t
mpn_toom54_mul_itch (mp_size_t an, mp_size_t bn)
{
  mp_size_t n = 1 + (4 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) / (size_t) 4);
  return 9 * n + 3;
}



#define mpn_toom42_mulmid_itch(n) (3 * (n) + GMP_NUMB_BITS)





#define mpn_fft_mul mpn_nussbaumer_mul
# 26 "hgcd_appr.c" 2
# 1 "../longlong.h" 1
# 43 "../longlong.h"
#define __BITS4 (W_TYPE_SIZE / 4)
#define __ll_B ((UWtype) 1 << (W_TYPE_SIZE / 2))
#define __ll_lowpart(t) ((UWtype) (t) & (__ll_B - 1))
#define __ll_highpart(t) ((UWtype) (t) >> (W_TYPE_SIZE / 2))
# 148 "../longlong.h"
#define count_leading_zeros_gcc_clz(count,x) do { ASSERT ((x) != 0); (count) = __builtin_clzl (x); } while (0)
# 162 "../longlong.h"
#define count_trailing_zeros_gcc_ctz(count,x) do { ASSERT ((x) != 0); (count) = __builtin_ctzl (x); } while (0)
# 374 "../longlong.h"
#define __CLOBBER_CC : "cc"
#define __AND_CLOBBER_CC , "cc"
# 997 "../longlong.h"
#define add_ssaaaa(sh,sl,ah,al,bh,bl) __asm__ ("addq %5,%q1\n\tadcq %3,%q0" : "=r" (sh), "=&r" (sl) : "0" ((UDItype)(ah)), "rme" ((UDItype)(bh)), "%1" ((UDItype)(al)), "rme" ((UDItype)(bl)))




#define sub_ddmmss(sh,sl,ah,al,bh,bl) __asm__ ("subq %5,%q1\n\tsbbq %3,%q0" : "=r" (sh), "=&r" (sl) : "0" ((UDItype)(ah)), "rme" ((UDItype)(bh)), "1" ((UDItype)(al)), "rme" ((UDItype)(bl)))




#define umul_ppmm(w1,w0,u,v) __asm__ ("mulq %3" : "=a" (w0), "=d" (w1) : "%0" ((UDItype)(u)), "rm" ((UDItype)(v)))



#define udiv_qrnnd(q,r,n1,n0,dx) __asm__ ("divq %4" : "=a" (q), "=d" (r) : "0" ((UDItype)(n0)), "1" ((UDItype)(n1)), "rm" ((UDItype)(dx)))




#define count_leading_zeros(count,x) do { UDItype __cbtmp; ASSERT ((x) != 0); __asm__ ("bsrq %1,%0" : "=r" (__cbtmp) : "rm" ((UDItype)(x))); (count) = __cbtmp ^ 63; } while (0)
# 1025 "../longlong.h"
#define count_trailing_zeros(count,x) do { ASSERT ((x) != 0); __asm__ ("bsfq %1,%q0" : "=r" (count) : "rm" ((UDItype)(x))); } while (0)
# 1846 "../longlong.h"
#define __umulsidi3(u,v) ({UWtype __hi, __lo; umul_ppmm (__hi, __lo, u, v); ((UDWtype) __hi << W_TYPE_SIZE) | __lo; })
# 1858 "../longlong.h"
#define mpn_umul_ppmm __MPN(umul_ppmm)
extern UWtype __gmpn_umul_ppmm (UWtype *, UWtype, UWtype);
# 1871 "../longlong.h"
#define mpn_umul_ppmm_r __MPN(umul_ppmm_r)
extern UWtype __gmpn_umul_ppmm_r (UWtype, UWtype, UWtype *);
# 1884 "../longlong.h"
#define mpn_udiv_qrnnd __MPN(udiv_qrnnd)
extern UWtype __gmpn_udiv_qrnnd (UWtype *, UWtype, UWtype, UWtype);
# 1898 "../longlong.h"
#define mpn_udiv_qrnnd_r __MPN(udiv_qrnnd_r)
extern UWtype __gmpn_udiv_qrnnd_r (UWtype, UWtype, UWtype, UWtype *);
# 1988 "../longlong.h"
#define smul_ppmm(w1,w0,u,v) do { UWtype __w1; UWtype __xm0 = (u), __xm1 = (v); umul_ppmm (__w1, w0, __xm0, __xm1); (w1) = __w1 - (-(__xm0 >> (W_TYPE_SIZE - 1)) & __xm1) - (-(__xm1 >> (W_TYPE_SIZE - 1)) & __xm0); } while (0)
# 1999 "../longlong.h"
#define __udiv_qrnnd_c(q,r,n1,n0,d) do { UWtype __d1, __d0, __q1, __q0, __r1, __r0, __m; ASSERT ((d) != 0); ASSERT ((n1) < (d)); __d1 = __ll_highpart (d); __d0 = __ll_lowpart (d); __q1 = (n1) / __d1; __r1 = (n1) - __q1 * __d1; __m = __q1 * __d0; __r1 = __r1 * __ll_B | __ll_highpart (n0); if (__r1 < __m) { __q1--, __r1 += (d); if (__r1 >= (d)) if (__r1 < __m) __q1--, __r1 += (d); } __r1 -= __m; __q0 = __r1 / __d1; __r0 = __r1 - __q0 * __d1; __m = __q0 * __d0; __r0 = __r0 * __ll_B | __ll_lowpart (n0); if (__r0 < __m) { __q0--, __r0 += (d); if (__r0 >= (d)) if (__r0 < __m) __q0--, __r0 += (d); } __r0 -= __m; (q) = __q1 * __ll_B | __q0; (r) = __r0; } while (0)
# 2133 "../longlong.h"
#define UDIV_NEEDS_NORMALIZATION 0





#define UDIV_PREINV_ALWAYS 0




#define UMUL_TIME 1



#define UDIV_TIME UMUL_TIME
# 27 "hgcd_appr.c" 2



mp_size_t
__gmpn_hgcd_appr_itch (mp_size_t n)
{
  if ((! ((__builtin_constant_p (400) && (400) == 0) || (!(__builtin_constant_p (400) && (400) == (-(((long) ((~ (unsigned long) 0) ^ ((unsigned long) (~ (unsigned long) 0) >> 1)))+1))) && (n) >= (400)))))
    return n;
  else
    {
      unsigned k;
      int count;
      mp_size_t nscaled;


      nscaled = (n - 1) / (400 - 1);
      do { UDItype __cbtmp; do {} while (0); __asm__ ("bsrq %1,%0" : "=r" (__cbtmp) : "rm" ((UDItype)(nscaled))); (count) = __cbtmp ^ 63; } while (0);
      k = 64 - count;

      return 20 * ((n+3) / 4) + 22 * k + ;
    }
}


int
__gmpn_hgcd_appr (mp_ptr ap, mp_ptr bp, mp_size_t n,
        struct hgcd_matrix *M, mp_ptr tp)
{
  mp_size_t s;
  int success = 0;

  do {} while (0);

  do {} while (0);

  if (n <= 2)


    return 0;

  do {} while (0);






  s = n/2 + 1;
  if ((! ((__builtin_constant_p (400) && (400) == 0) || (!(__builtin_constant_p (400) && (400) == (-(((long) ((~ (unsigned long) 0) ^ ((unsigned long) (~ (unsigned long) 0) >> 1)))+1))) && (n) >= (400)))))
    {
      unsigned extra_bits = 0;

      while (n > 2)
 {
   mp_size_t nn;

   do {} while (0);
   do {} while (0);

   nn = __gmpn_hgcd_step (n, ap, bp, s, M, tp);
   if (!nn)
     break;

   n = nn;
   success = 1;
# 102 "hgcd_appr.c"
   if ((64 - 0) * (n + 1) + 2 * extra_bits <= 2*(64 - 0) * s)
     {
       mp_size_t p = ((64 - 0) * (2*s - n) - 2*extra_bits) / (64 - 0);

       if (extra_bits == 0)
  {



    if (s + 1 == n
        || mpn_zero_p (ap + s + 1, n - s - 1)
        || mpn_zero_p (bp + s + 1, n - s - 1))
      continue;

    extra_bits = (64 - 0) - 1;
    s++;
  }
       else
  {
    extra_bits--;
  }


       ap += p; bp += p; n -= p; s -= p;
     }
 }

      do {} while (0);

      if (extra_bits > 0)
 {
# 141 "hgcd_appr.c"
   ap--; bp--;
   ap[0] = __gmpn_rshift (ap+1, ap+1, n, (64 - 0) - extra_bits);
   bp[0] = __gmpn_rshift (bp+1, bp+1, n, (64 - 0) - extra_bits);
   n += (ap[n] | bp[n]) > 0;

   do {} while (0);

   while (n > 2)
     {
       mp_size_t nn;

       do {} while (0);
       do {} while (0);

       nn = __gmpn_hgcd_step (n, ap, bp, s, M, tp);

       if (!nn)
  return 1;

       n = nn;
     }
 }

      if (n == 2)
 {
   struct hgcd_matrix1 M1;
   do {} while (0);

   if (__gmpn_hgcd2 (ap[1], ap[0], bp[1], bp[0], &M1))
     {

       __gmpn_hgcd_matrix_mul_1 (M, &M1, tp);
       success = 1;
     }
 }
      return success;
    }
  else
    {
      mp_size_t n2 = (3*n)/4 + 1;
      mp_size_t p = n/2;
      mp_size_t nn;

      nn = __gmpn_hgcd_reduce (M, ap, bp, n, p, tp);
      if (nn)
 {
   n = nn;

   success = 1;
 }

      while (n > n2)
 {
   mp_size_t nn;


   nn = __gmpn_hgcd_step (n, ap, bp, s, M, tp);
   if (!nn)
     return success;

   n = nn;
   success = 1;
 }
      if (n > s + 2)
 {
   struct hgcd_matrix M1;
   mp_size_t scratch;

   p = 2*s - n + 1;
   scratch = (4 * ((n-p+1)/2 + 1));

   __gmpn_hgcd_matrix_init(&M1, n - p, tp);
   if (__gmpn_hgcd_appr (ap + p, bp + p, n - p, &M1, tp + scratch))
     {

       do {} while (0);







       do {} while (0);
# 237 "hgcd_appr.c"
       __gmpn_hgcd_matrix_mul (M, &M1, tp + scratch);
       return 1;
     }
 }

      for(;;)
 {
   mp_size_t nn;

   do {} while (0);
   do {} while (0);

   nn = __gmpn_hgcd_step (n, ap, bp, s, M, tp);

   if (!nn)
     return success;

   n = nn;
   success = 1;
 }
    }
}