191215

Ruby


逆元の求め方

p が素数のとき、
1~p-1 までの逆元(mod p) を求める楽な方法を紹介します。

0 < a < n で、a, n が互いに素とします。
n = x * a + (n % a)
と書けます。
すなわち
x * a + (n % a) == 0 (mod n)
よって、x + (n % a) * a^(-1) == 0  (mod n)
ゆえに、a^(-1) == - (n % a)^(-1) * x  (mod n)

この式の有難い点は
(n % a)^(-1) が分かっていれば、
a^(-1) が分かるという点です。
n が素数の時、逆元が次々と求めることができるわけです。

require 'prime'

def A124223(p)
  a = [0, 1]
  (2..p - 1).each{|i| a << (-a[p % i] * (p / i)) % p}
  a[1..-1]
end

p Prime.each(200).map{|i| A124223(i)}.flatten

出力結果
[1, 1, 2, 1, 3, 2, 4, 1, 4, 5, 2, 3, 6, 1, 6, 4, 3, 9, 2, 8, 7, 5, 10, 1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12, 1, 9, 6, 13, 7, 3, 5, 15, 2, 12, 14, 10, 4, 11, 8, 16, 1, 10, 13, 5, 4, 16, 11, 12, 17, 2, 7, 8, 3, 15, 14, 6, 9, 18, 1, 12, 8, 6, 14, 4, 10, 3, 18, 7, 21, 2, 16, 5, 20, 13, 19, 9, 17, 15, 11, 22, 1, 15, 10, 22, 6, 5, 25, 11, 13, 3, 8, 17, 9, 27, 2, 20, 12, 21, 26, 16, 18, 4, 24, 23, 7, 19, 14, 28, 1, 16, 21, 8, 25, 26, 9, 4, 7, 28, 17, 13, 12, 20, 29, 2, 11, 19, 18, 14, 3, 24, 27, 22, 5, 6, 23, 10, 15, 30, 1, 19, 25, 28, 15, 31, 16, 14, 33, 26, 27, 34, 20, 8, 5, 7, 24, 35, 2, 13, 30, 32, 29, 17, 3, 10, 11, 4, 23, 21, 6, 22, 9, 12, 18, 36, 1, 21, 14, 31, 33, 7, 6, 36, 32, 37, 15, 24, 19, 3, 11, 18, 29, 16, 13, 39, 2, 28, 25, 12, 23, 30, 38, 22, 17, 26, 4, 9, 5, 35, 34, 8, 10, 27, 20, 40, 1, 22, 29, 11, 26, 36, 37, 27, 24, 13, 4, 18, 10, 40, 23, 35, 38, 12, 34, 28, 41, 2, 15, 9, 31, 5, 8, 20, 3, 33, 25, 39, 30, 19, 16, 6, 7, 17, 32, 14, 21, 42, 1, 24, 16, 12, 19, 8, 27, 6, 21, 33, 30, 4, 29, 37, 22, 3, 36, 34, 5, 40, 9, 15, 45, 2, 32, 38, 7, 42, 13, 11, 44, 25, 10, 18, 43, 17, 14, 26, 41, 20, 39, 28, 35, 31, 23, 46, 1, 27, 18, 40, 32, 9, 38, 20, 6, 16, 29, 31, 49, 19, 46, 10, 25, 3, 14, 8, 48, 41, 30, 42, 17, 51, 2, 36, 11, 23, 12, 5, 45, 39, 50, 28, 43, 7, 34, 4, 22, 24, 37, 47, 33, 15, 44, 21, 13, 35, 26, 52, 1, 30, 20, 15, 12, 10, 17, 37, 46, 6, 43, 5, 50, 38, 4, 48, 7, 23, 28, 3, 45, 51, 18, 32, 26, 25, 35, 19, 57, 2, 40, 24, 34, 33, 27, 41, 8, 14, 56, 31, 36, 52, 11, 55, 21, 9, 54, 16, 53, 13, 22, 42, 49, 47, 44, 39, 29, 58, 1, 31, 41, 46, 49, 51, 35, 23, 34, 55, 50, 56, 47, 48, 57, 42, 18, 17, 45, 58, 32, 25, 8, 28, 22, 54, 52, 24, 40, 59, 2, 21, 37, 9, 7, 39, 33, 53, 36, 29, 3, 16, 44, 43, 19, 4, 13, 14, 5, 11, 6, 27, 38, 26, 10, 12, 15, 20, 30, 60, 1, 34, 45, 17, 27, 56, 48, 42, 15, 47, 61, 28, 31, 24, 9, 21, 4, 41, 60, 57, 16, 64, 35, 14, 59, 49, 5, 12, 37, 38, 13, 44, 65, 2, 23, 54, 29, 30, 55, 62, 18, 8, 53, 32, 3, 51, 10, 7, 26, 63, 46, 58, 43, 36, 39, 6, 20, 52, 25, 19, 11, 40, 50, 22, 33, 66, 1, 36, 24, 18, 57, 12, 61, 9, 8, 64, 13, 6, 11, 66, 19, 40, 46, 4, 15, 32, 44, 42, 34, 3, 54, 41, 50, 33, 49, 45, 55, 20, 28, 23, 69, 2, 48, 43, 51, 16, 26, 22, 38, 21, 30, 17, 68, 37, 29, 27, 39, 56, 67, 25, 31, 52, 5, 60, 65, 58, 7, 63, 62, 10, 59, 14, 53, 47, 35, 70, 1, 37, 49, 55, 44, 61, 21, 64, 65, 22, 20, 67, 45, 47, 39, 32, 43, 69, 50, 11, 7, 10, 54, 70, 38, 59, 46, 60, 68, 56, 33, 16, 31, 58, 48, 71, 2, 25, 15, 42, 57, 40, 17, 5, 13, 27, 14, 35, 3, 19, 63, 66, 62, 23, 4, 30, 41, 34, 26, 28, 6, 53, 51, 8, 9, 52, 12, 29, 18, 24, 36, 72, 1, 40, 53, 20, 16, 66, 34, 10, 44, 8, 36, 33, 73, 17, 58, 5, 14, 22, 25, 4, 64, 18, 55, 56, 19, 76, 41, 48, 30, 29, 51, 42, 12, 7, 70, 11, 47, 52, 77, 2, 27, 32, 68, 9, 72, 67, 37, 28, 50, 49, 31, 38, 3, 60, 23, 24, 61, 15, 75, 54, 57, 65, 74, 21, 62, 6, 46, 43, 71, 35, 69, 45, 13, 63, 59, 26, 39, 78, 1, 42, 28, 21, 50, 14, 12, 52, 37, 25, 68, 7, 32, 6, 72, 26, 44, 60, 35, 54, 4, 34, 65, 45, 10, 16, 40, 3, 63, 36, 75, 13, 78, 22, 19, 30, 9, 59, 66, 27, 81, 2, 56, 17, 24, 74, 53, 64, 61, 5, 70, 8, 47, 20, 80, 43, 67, 73, 38, 18, 49, 79, 29, 48, 23, 39, 57, 11, 77, 51, 76, 15, 58, 46, 31, 71, 69, 33, 62, 55, 41, 82, 1, 45, 30, 67, 18, 15, 51, 78, 10, 9, 81, 52, 48, 70, 6, 39, 21, 5, 75, 49, 17, 85, 31, 26, 57, 24, 33, 35, 43, 3, 23, 64, 27, 55, 28, 47, 77, 82, 16, 69, 76, 53, 29, 87, 2, 60, 36, 13, 20, 73, 7, 12, 42, 61, 34, 62, 25, 66, 86, 46, 54, 56, 65, 32, 63, 58, 4, 72, 40, 14, 84, 68, 50, 83, 19, 41, 37, 8, 80, 79, 11, 38, 74, 71, 22, 59, 44, 88, 1, 49, 65, 73, 39, 81, 14, 85, 54, 68, 53, 89, 15, 7, 13, 91, 40, 27, 46, 34, 37, 75, 38, 93, 66, 56, 18, 52, 87, 55, 72, 94, 50, 20, 61, 62, 21, 23, 5, 17, 71, 67, 88, 86, 69, 19, 64, 95, 2, 33, 78, 28, 11, 9, 30, 26, 80, 92, 74, 76, 35, 36, 77, 47, 3, 25, 42, 10, 45, 79, 41, 31, 4, 59, 22, 60, 63, 51, 70, 57, 6, 84, 90, 82, 8, 44, 29, 43, 12, 83, 16, 58, 24, 32, 48, 96, 1, 51, 34, 76, 81, 17, 29, 38, 45, 91, 46, 59, 70, 65, 27, 19, 6, 73, 16, 96, 77, 23, 22, 80, 97, 35, 15, 83, 7, 64, 88, 60, 49, 3, 26, 87, 71, 8, 57, 48, 69, 89, 47, 62, 9, 11, 43, 40, 33, 99, 2, 68, 61, 58, 90, 92, 39, 54, 12, 32, 53, 44, 93, 30, 14, 75, 98, 52, 41, 13, 37, 94, 18, 86, 66, 4, 21, 79, 78, 24, 5, 85, 28, 95, 82, 74, 36, 31, 42, 55, 10, 56, 63, 72, 84, 20, 25, 67, 50, 100, 1, 52, 69, 26, 62, 86, 59, 13, 23, 31, 75, 43, 8, 81, 55, 58, 97, 63, 38, 67, 54, 89, 9, 73, 33, 4, 42, 92, 32, 79, 10, 29, 25, 100, 53, 83, 39, 19, 37, 85, 98, 27, 12, 96, 87, 56, 57, 88, 82, 68, 101, 2, 35, 21, 15, 46, 47, 16, 7, 91, 76, 5, 18, 66, 84, 64, 20, 50, 3, 78, 74, 93, 24, 71, 11, 61, 99, 70, 30, 94, 14, 49, 36, 65, 40, 6, 45, 48, 22, 95, 60, 28, 72, 80, 90, 44, 17, 41, 77, 34, 51, 102, 1, 54, 36, 27, 43, 18, 46, 67, 12, 75, 39, 9, 33, 23, 50, 87, 63, 6, 62, 91, 51, 73, 14, 58, 30, 70, 4, 65, 48, 25, 38, 97, 13, 85, 52, 3, 81, 31, 11, 99, 47, 79, 5, 90, 88, 7, 41, 29, 83, 15, 21, 35, 105, 2, 72, 86, 92, 24, 78, 66, 100, 19, 17, 102, 28, 60, 8, 96, 76, 26, 104, 55, 22, 94, 10, 69, 82, 59, 42, 103, 37, 77, 49, 93, 34, 56, 16, 45, 101, 44, 20, 57, 84, 74, 98, 68, 32, 95, 40, 61, 89, 64, 80, 71, 53, 106, 1, 55, 73, 82, 22, 91, 78, 41, 97, 11, 10, 100, 42, 39, 80, 75, 77, 103, 23, 60, 26, 5, 19, 50, 48, 21, 105, 74, 94, 40, 102, 92, 76, 93, 81, 106, 56, 66, 14, 30, 8, 13, 71, 57, 63, 64, 58, 25, 89, 24, 62, 65, 72, 107, 2, 37, 44, 47, 85, 20, 84, 51, 45, 46, 52, 38, 96, 101, 79, 95, 43, 53, 3, 28, 16, 33, 17, 7, 69, 15, 35, 4, 88, 61, 59, 90, 104, 83, 49, 86, 6, 32, 34, 29, 70, 67, 9, 99, 98, 12, 68, 31, 18, 87, 27, 36, 54, 108, 1, 57, 38, 85, 68, 19, 97, 99, 88, 34, 72, 66, 87, 105, 98, 106, 20, 44, 6, 17, 70, 36, 59, 33, 104, 100, 67, 109, 39, 49, 62, 53, 24, 10, 42, 22, 55, 3, 29, 65, 102, 35, 92, 18, 108, 86, 101, 73, 30, 52, 82, 50, 32, 90, 37, 111, 2, 76, 23, 81, 63, 31, 61, 83, 40, 12, 27, 5, 95, 21, 78, 11, 48, 84, 110, 58, 91, 71, 103, 89, 60, 51, 64, 74, 4, 46, 13, 9, 80, 54, 77, 43, 96, 107, 69, 93, 7, 15, 8, 26, 47, 41, 79, 25, 14, 16, 94, 45, 28, 75, 56, 112, 1, 64, 85, 32, 51, 106, 109, 16, 113, 89, 104, 53, 88, 118, 17, 8, 15, 120, 107, 108, 121, 52, 116, 90, 61, 44, 80, 59, 92, 72, 41, 4, 77, 71, 98, 60, 103, 117, 114, 54, 31, 124, 65, 26, 48, 58, 100, 45, 70, 94, 5, 22, 12, 40, 97, 93, 78, 46, 28, 36, 25, 84, 125, 2, 43, 102, 91, 99, 81, 49, 34, 30, 87, 115, 105, 122, 33, 57, 82, 27, 69, 79, 101, 62, 3, 96, 73, 13, 10, 24, 67, 29, 56, 50, 123, 86, 55, 35, 68, 47, 83, 66, 37, 11, 75, 6, 19, 20, 7, 112, 119, 110, 9, 39, 74, 23, 38, 14, 111, 18, 21, 76, 95, 42, 63, 126, 1, 66, 44, 33, 105, 22, 75, 82, 102, 118, 12, 11, 121, 103, 35, 41, 54, 51, 69, 59, 25, 6, 57, 71, 21, 126, 34, 117, 122, 83, 93, 86, 4, 27, 15, 91, 85, 100, 84, 95, 16, 78, 64, 3, 99, 94, 92, 101, 123, 76, 18, 63, 89, 17, 81, 124, 23, 61, 20, 107, 58, 112, 52, 43, 129, 2, 88, 79, 19, 73, 24, 111, 70, 108, 7, 50, 114, 42, 68, 113, 55, 8, 30, 39, 37, 32, 128, 67, 53, 115, 36, 47, 31, 46, 40, 116, 104, 127, 45, 38, 48, 9, 14, 97, 5, 110, 60, 74, 125, 106, 72, 62, 80, 77, 90, 96, 28, 10, 120, 119, 13, 29, 49, 56, 109, 26, 98, 87, 65, 130, 1, 69, 46, 103, 55, 23, 98, 120, 61, 96, 25, 80, 116, 49, 64, 60, 129, 99, 101, 48, 124, 81, 6, 40, 11, 58, 66, 93, 52, 32, 84, 30, 54, 133, 47, 118, 100, 119, 130, 24, 127, 62, 51, 109, 67, 3, 35, 20, 14, 74, 43, 29, 106, 33, 5, 115, 125, 26, 72, 16, 9, 42, 87, 15, 78, 27, 45, 135, 2, 92, 110, 59, 122, 50, 95, 128, 121, 65, 111, 12, 22, 132, 104, 31, 108, 94, 63, 123, 117, 102, 134, 70, 28, 86, 75, 10, 113, 7, 18, 37, 19, 90, 4, 83, 107, 53, 105, 85, 44, 71, 79, 126, 97, 131, 56, 13, 89, 36, 38, 8, 77, 73, 88, 21, 57, 112, 41, 76, 17, 39, 114, 82, 34, 91, 68, 136, 1, 70, 93, 35, 28, 116, 20, 87, 31, 14, 38, 58, 107, 10, 102, 113, 90, 85, 22, 7, 53, 19, 133, 29, 89, 123, 103, 5, 24, 51, 9, 126, 59, 45, 4, 112, 124, 11, 82, 73, 78, 96, 97, 79, 34, 136, 71, 84, 122, 114, 30, 131, 21, 121, 91, 72, 100, 12, 33, 95, 98, 74, 64, 63, 77, 99, 83, 92, 137, 2, 47, 56, 40, 62, 76, 75, 65, 41, 44, 106, 127, 39, 67, 48, 18, 118, 8, 109, 25, 17, 55, 68, 3, 105, 60, 42, 43, 61, 66, 57, 128, 15, 27, 135, 94, 80, 13, 130, 88, 115, 134, 36, 16, 50, 110, 6, 120, 86, 132, 117, 54, 49, 26, 37, 129, 32, 81, 101, 125, 108, 52, 119, 23, 111, 104, 46, 69, 138, 1, 75, 50, 112, 30, 25, 64, 56, 116, 15, 122, 87, 23, 32, 10, 28, 114, 58, 102, 82, 71, 61, 13, 118, 6, 86, 138, 16, 36, 5, 125, 14, 140, 57, 132, 29, 145, 51, 107, 41, 40, 110, 52, 105, 53, 81, 130, 59, 73, 3, 38, 43, 45, 69, 84, 8, 34, 18, 48, 77, 22, 137, 123, 7, 94, 70, 129, 103, 54, 66, 21, 89, 49, 147, 2, 100, 60, 128, 83, 95, 46, 20, 79, 55, 142, 26, 12, 127, 72, 101, 131, 115, 141, 65, 80, 104, 106, 111, 146, 76, 90, 19, 68, 96, 44, 97, 39, 109, 108, 42, 98, 4, 120, 17, 92, 9, 135, 24, 144, 113, 133, 11, 63, 143, 31, 136, 88, 78, 67, 47, 91, 35, 121, 139, 117, 126, 62, 27, 134, 33, 93, 85, 124, 119, 37, 99, 74, 148, 1, 76, 101, 38, 121, 126, 108, 19, 84, 136, 55, 63, 93, 54, 141, 85, 80, 42, 8, 68, 36, 103, 46, 107, 145, 122, 28, 27, 125, 146, 39, 118, 119, 40, 82, 21, 49, 4, 31, 34, 70, 18, 144, 127, 47, 23, 45, 129, 37, 148, 77, 61, 57, 14, 11, 89, 53, 138, 64, 73, 52, 95, 12, 59, 79, 135, 142, 20, 116, 41, 134, 86, 60, 100, 149, 2, 51, 91, 65, 17, 110, 35, 131, 9, 16, 72, 92, 139, 56, 99, 78, 87, 13, 98, 62, 140, 137, 94, 90, 74, 3, 114, 22, 106, 128, 104, 24, 7, 133, 81, 117, 120, 147, 102, 130, 69, 111, 32, 33, 112, 5, 26, 124, 123, 29, 6, 44, 105, 48, 115, 83, 143, 109, 71, 66, 10, 97, 58, 88, 96, 15, 67, 132, 43, 25, 30, 113, 50, 75, 150, 1, 79, 105, 118, 63, 131, 45, 59, 35, 110, 100, 144, 145, 101, 21, 108, 37, 96, 124, 55, 15, 50, 41, 72, 44, 151, 64, 129, 65, 89, 76, 54, 138, 97, 9, 48, 17, 62, 153, 106, 23, 86, 84, 25, 7, 99, 147, 36, 141, 22, 117, 154, 80, 32, 20, 143, 146, 111, 8, 123, 139, 38, 5, 27, 29, 69, 75, 127, 66, 83, 115, 24, 114, 87, 67, 31, 104, 155, 2, 53, 126, 90, 70, 43, 133, 42, 74, 91, 30, 82, 88, 128, 130, 152, 119, 18, 34, 149, 46, 11, 14, 137, 125, 77, 3, 40, 135, 16, 121, 10, 58, 150, 132, 73, 71, 134, 51, 4, 95, 140, 109, 148, 60, 19, 103, 81, 68, 92, 28, 93, 6, 113, 85, 116, 107, 142, 102, 33, 61, 120, 49, 136, 56, 12, 13, 57, 47, 122, 98, 112, 26, 94, 39, 52, 78, 156, 1, 82, 109, 41, 98, 136, 70, 102, 145, 49, 89, 68, 138, 35, 87, 51, 48, 154, 103, 106, 132, 126, 78, 34, 150, 69, 157, 99, 45, 125, 142, 107, 84, 24, 14, 77, 141, 133, 46, 53, 4, 66, 91, 63, 29, 39, 111, 17, 10, 75, 16, 116, 40, 160, 83, 131, 143, 104, 105, 144, 155, 71, 44, 135, 158, 42, 73, 12, 26, 7, 62, 120, 67, 152, 50, 148, 36, 23, 130, 108, 161, 2, 55, 33, 140, 127, 15, 113, 11, 96, 43, 101, 156, 137, 151, 90, 121, 5, 28, 119, 92, 8, 19, 58, 59, 20, 32, 80, 3, 123, 47, 147, 88, 153, 146, 52, 124, 134, 100, 72, 97, 159, 110, 117, 30, 22, 86, 149, 139, 79, 56, 21, 38, 118, 64, 6, 94, 13, 129, 85, 37, 31, 57, 60, 9, 115, 112, 76, 128, 25, 95, 74, 114, 18, 61, 93, 27, 65, 122, 54, 81, 162, 1, 84, 56, 42, 67, 28, 24, 21, 130, 117, 76, 14, 90, 12, 78, 94, 59, 65, 44, 142, 8, 38, 138, 7, 147, 45, 99, 6, 144, 39, 97, 47, 81, 113, 105, 116, 158, 22, 30, 71, 110, 4, 101, 19, 26, 69, 32, 87, 75, 157, 131, 106, 104, 133, 82, 3, 126, 72, 17, 103, 115, 132, 114, 107, 18, 124, 5, 140, 46, 136, 40, 58, 151, 79, 49, 11, 154, 15, 74, 119, 33, 55, 165, 2, 112, 134, 48, 93, 152, 13, 156, 118, 88, 16, 109, 127, 31, 121, 27, 162, 43, 149, 60, 53, 35, 52, 64, 150, 95, 41, 164, 85, 34, 63, 61, 36, 10, 92, 80, 135, 98, 141, 148, 66, 163, 57, 96, 137, 145, 9, 51, 62, 54, 86, 120, 70, 128, 23, 161, 68, 122, 20, 160, 29, 129, 159, 25, 123, 102, 108, 73, 89, 155, 77, 153, 91, 50, 37, 146, 143, 139, 100, 125, 111, 83, 166, 1, 87, 58, 130, 104, 29, 99, 65, 77, 52, 63, 101, 40, 136, 150, 119, 112, 125, 82, 26, 33, 118, 158, 137, 90, 20, 141, 68, 6, 75, 67, 146, 21, 56, 89, 149, 159, 41, 71, 13, 38, 103, 169, 59, 50, 79, 81, 155, 113, 45, 95, 10, 111, 157, 151, 34, 85, 3, 44, 124, 156, 120, 11, 73, 8, 97, 31, 28, 168, 131, 39, 161, 64, 166, 30, 107, 9, 122, 46, 93, 47, 19, 148, 138, 57, 171, 2, 116, 35, 25, 154, 126, 80, 127, 51, 164, 66, 143, 7, 109, 12, 134, 42, 5, 145, 142, 76, 165, 100, 162, 53, 17, 49, 129, 170, 88, 139, 22, 16, 62, 163, 78, 128, 60, 18, 92, 94, 123, 114, 4, 70, 135, 160, 102, 132, 14, 24, 84, 117, 152, 27, 106, 98, 167, 105, 32, 153, 83, 36, 15, 55, 140, 147, 91, 48, 61, 54, 23, 37, 133, 72, 110, 121, 96, 108, 74, 144, 69, 43, 115, 86, 172, 1, 90, 60, 45, 36, 30, 128, 112, 20, 18, 114, 15, 124, 64, 12, 56, 158, 10, 66, 9, 162, 57, 109, 97, 43, 62, 126, 32, 142, 6, 52, 28, 38, 79, 133, 5, 150, 33, 101, 94, 131, 81, 25, 118, 4, 144, 80, 138, 95, 111, 172, 31, 152, 63, 166, 16, 22, 71, 88, 3, 135, 26, 54, 14, 168, 19, 171, 129, 96, 156, 58, 92, 103, 75, 74, 106, 93, 140, 34, 47, 42, 155, 110, 130, 139, 102, 107, 59, 177, 2, 120, 72, 77, 40, 49, 69, 24, 137, 132, 145, 39, 86, 73, 105, 104, 76, 87, 121, 23, 83, 50, 8, 160, 11, 165, 125, 153, 44, 176, 91, 108, 157, 163, 13, 116, 27, 148, 7, 68, 84, 41, 99, 35, 175, 61, 154, 98, 48, 85, 78, 146, 29, 174, 46, 100, 141, 151, 127, 173, 37, 147, 53, 117, 136, 82, 70, 122, 17, 170, 113, 169, 21, 123, 167, 115, 55, 164, 65, 161, 159, 67, 51, 149, 143, 134, 119, 89, 178, 1, 91, 121, 136, 145, 151, 26, 68, 161, 163, 33, 166, 14, 13, 169, 34, 32, 171, 162, 172, 69, 107, 63, 83, 29, 7, 114, 97, 25, 175, 146, 17, 11, 16, 150, 176, 137, 81, 65, 86, 53, 125, 80, 144, 177, 122, 104, 132, 133, 105, 71, 94, 41, 57, 79, 139, 54, 103, 135, 178, 92, 73, 23, 99, 39, 96, 154, 8, 21, 75, 51, 88, 62, 159, 70, 131, 134, 123, 55, 43, 38, 117, 24, 153, 115, 40, 129, 72, 120, 179, 2, 61, 109, 52, 141, 66, 28, 157, 64, 143, 138, 126, 58, 47, 50, 111, 22, 119, 93, 130, 106, 160, 173, 27, 85, 142, 82, 158, 108, 89, 3, 46, 78, 127, 42, 102, 124, 140, 87, 110, 76, 48, 49, 77, 59, 4, 37, 101, 56, 128, 95, 116, 100, 44, 5, 31, 165, 170, 164, 35, 6, 156, 84, 67, 174, 152, 98, 118, 74, 112, 9, 19, 10, 149, 147, 12, 168, 167, 15, 148, 18, 20, 113, 155, 30, 36, 45, 60, 90, 180, 1, 96, 64, 48, 153, 32, 82, 24, 85, 172, 139, 16, 147, 41, 51, 12, 45, 138, 181, 86, 91, 165, 108, 8, 107, 169, 92, 116, 112, 121, 37, 6, 110, 118, 131, 69, 31, 186, 49, 43, 14, 141, 40, 178, 17, 54, 126, 4, 39, 149, 15, 180, 173, 46, 66, 58, 124, 56, 68, 156, 119, 114, 94, 3, 144, 55, 134, 59, 36, 161, 113, 130, 157, 111, 163, 93, 129, 120, 162, 117, 158, 7, 168, 166, 9, 20, 101, 89, 88, 104, 21, 27, 76, 63, 189, 2, 128, 115, 164, 170, 87, 103, 102, 90, 171, 182, 25, 23, 184, 33, 74, 29, 71, 62, 98, 28, 80, 34, 61, 78, 30, 155, 132, 57, 136, 47, 188, 97, 77, 72, 35, 123, 135, 67, 133, 125, 145, 18, 11, 176, 42, 152, 187, 65, 137, 174, 13, 151, 50, 177, 148, 142, 5, 160, 122, 60, 73, 81, 185, 154, 70, 79, 75, 99, 22, 84, 183, 83, 26, 100, 105, 10, 53, 146, 179, 140, 150, 44, 175, 52, 19, 106, 167, 109, 159, 38, 143, 127, 95, 190, 1, 97, 129, 145, 116, 161, 138, 169, 43, 58, 158, 177, 104, 69, 103, 181, 159, 118, 61, 29, 46, 79, 42, 185, 139, 52, 143, 131, 20, 148, 137, 187, 117, 176, 182, 59, 120, 127, 99, 111, 113, 23, 9, 136, 163, 21, 115, 189, 130, 166, 53, 26, 51, 168, 186, 162, 149, 10, 36, 74, 19, 165, 144, 190, 98, 155, 121, 88, 14, 91, 87, 126, 156, 60, 175, 160, 188, 146, 22, 152, 112, 153, 100, 108, 109, 101, 71, 68, 180, 178, 70, 107, 110, 154, 128, 191, 2, 65, 39, 83, 86, 123, 15, 13, 125, 122, 92, 84, 85, 93, 40, 81, 41, 171, 47, 5, 33, 18, 133, 37, 67, 106, 102, 179, 105, 72, 38, 95, 3, 49, 28, 174, 119, 157, 183, 44, 31, 7, 25, 142, 167, 140, 27, 63, 4, 78, 172, 30, 57, 184, 170, 80, 82, 94, 66, 73, 134, 11, 17, 76, 6, 56, 45, 173, 62, 50, 141, 54, 8, 151, 114, 147, 164, 132, 75, 34, 12, 90, 124, 89, 16, 35, 135, 150, 24, 55, 32, 77, 48, 64, 96, 192, 1, 99, 66, 148, 79, 33, 169, 74, 22, 138, 18, 115, 91, 183, 92, 37, 58, 11, 83, 69, 122, 9, 60, 156, 134, 144, 73, 190, 34, 46, 89, 117, 6, 29, 152, 104, 16, 140, 96, 133, 173, 61, 55, 103, 162, 30, 109, 78, 193, 67, 85, 72, 171, 135, 43, 95, 159, 17, 187, 23, 42, 143, 172, 157, 97, 3, 50, 113, 20, 76, 111, 52, 27, 8, 176, 70, 87, 48, 5, 165, 90, 185, 19, 129, 51, 126, 77, 150, 31, 81, 13, 15, 161, 153, 56, 39, 65, 195, 2, 132, 158, 141, 44, 36, 182, 184, 116, 166, 47, 120, 71, 146, 68, 178, 12, 107, 32, 192, 149, 110, 127, 21, 189, 170, 145, 86, 121, 177, 84, 147, 194, 100, 40, 25, 54, 155, 174, 10, 180, 38, 102, 154, 62, 26, 125, 112, 130, 4, 119, 88, 167, 35, 94, 142, 136, 24, 64, 101, 57, 181, 93, 45, 168, 191, 80, 108, 151, 163, 7, 124, 53, 63, 41, 137, 188, 75, 128, 114, 186, 139, 160, 105, 14, 106, 82, 179, 59, 175, 123, 28, 164, 118, 49, 131, 98, 196, 1, 100, 133, 50, 40, 166, 57, 25, 177, 20, 181, 83, 46, 128, 146, 112, 82, 188, 21, 10, 19, 190, 26, 141, 8, 23, 59, 64, 151, 73, 122, 56, 193, 41, 91, 94, 156, 110, 148, 5, 34, 109, 162, 95, 115, 13, 72, 170, 65, 4, 160, 111, 184, 129, 76, 32, 7, 175, 27, 136, 62, 61, 139, 28, 49, 196, 101, 120, 75, 145, 185, 47, 30, 78, 69, 55, 168, 74, 131, 102, 86, 17, 12, 154, 96, 81, 183, 147, 161, 157, 35, 106, 107, 36, 44, 85, 119, 132, 197, 2, 67, 80, 114, 155, 163, 92, 93, 164, 42, 38, 52, 16, 118, 103, 45, 187, 182, 113, 97, 68, 125, 31, 144, 130, 121, 169, 152, 14, 54, 124, 79, 98, 3, 150, 171, 60, 138, 137, 63, 172, 24, 192, 167, 123, 70, 15, 88, 39, 195, 134, 29, 127, 186, 84, 104, 37, 90, 165, 194, 51, 89, 43, 105, 108, 158, 6, 143, 77, 126, 48, 135, 140, 176, 191, 58, 173, 9, 180, 189, 178, 11, 117, 87, 53, 71, 153, 116, 18, 179, 22, 174, 142, 33, 159, 149, 66, 99, 198]