; LLVM IR from tangjz/acm-icpc :: 51nod (1362)

; Unoptimized IR (clang -disable-llvm-passes):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@n = external dso_local global i32, align 4
@m = external dso_local global i32, align 4
@p = external dso_local global i32, align 4
@c = external dso_local global [801 x [801 x i32]], align 16
@ans = external dso_local global i32, align 4
@tot = external dso_local global i32, align 4
@prime = external dso_local global [32000 x i32], align 16
@cnt = external dso_local global i32, align 4
@fact = external dso_local global [10 x i32], align 16
@exp = external dso_local global [10 x i32], align 16
@coeff = external dso_local global i32, align 4
@vis = external dso_local global [32000 x i8], align 16
@.str = external hidden unnamed_addr constant [7 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [4 x i8], align 1

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_Z7mod_invi(i32 noundef) #0

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef i32 @_Z7mod_powii(i32 noundef, i32 noundef) #2

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() #3 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = alloca i32, align 4
  %7 = alloca i32, align 4
  %8 = alloca i32, align 4
  %9 = alloca i32, align 4
  %10 = alloca i32, align 4
  %11 = alloca i32, align 4
  %12 = alloca i32, align 4
  %13 = alloca i32, align 4
  %14 = alloca i32, align 4
  %15 = alloca i32, align 4
  %16 = alloca i32, align 4
  %17 = alloca i32, align 4
  %18 = alloca i32, align 4
  %19 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  call void @llvm.lifetime.start.p0(i64 4, ptr %2) #5
  store i32 2, ptr %2, align 4, !tbaa !5
  br label %20

20:                                               ; preds = %70, %0
  %21 = load i32, ptr %2, align 4, !tbaa !5
  %22 = icmp slt i32 %21, 32000
  br i1 %22, label %24, label %23

23:                                               ; preds = %20
  store i32 2, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %2) #5
  br label %73

24:                                               ; preds = %20
  %25 = load i32, ptr %2, align 4, !tbaa !5
  %26 = sext i32 %25 to i64
  %27 = getelementptr inbounds [32000 x i8], ptr @vis, i64 0, i64 %26
  %28 = load i8, ptr %27, align 1, !tbaa !9, !range !11, !noundef !12
  %29 = trunc i8 %28 to i1
  br i1 %29, label %36, label %30

30:                                               ; preds = %24
  %31 = load i32, ptr %2, align 4, !tbaa !5
  %32 = load i32, ptr @tot, align 4, !tbaa !5
  %33 = add nsw i32 %32, 1
  store i32 %33, ptr @tot, align 4, !tbaa !5
  %34 = sext i32 %32 to i64
  %35 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %34
  store i32 %31, ptr %35, align 4, !tbaa !5
  br label %36

36:                                               ; preds = %30, %24
  call void @llvm.lifetime.start.p0(i64 4, ptr %4) #5
  store i32 0, ptr %4, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %5) #5
  br label %37

37:                                               ; preds = %65, %36
  %38 = load i32, ptr %4, align 4, !tbaa !5
  %39 = load i32, ptr @tot, align 4, !tbaa !5
  %40 = icmp slt i32 %38, %39
  br i1 %40, label %41, label %49

41:                                               ; preds = %37
  %42 = load i32, ptr %2, align 4, !tbaa !5
  %43 = load i32, ptr %4, align 4, !tbaa !5
  %44 = sext i32 %43 to i64
  %45 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %44
  %46 = load i32, ptr %45, align 4, !tbaa !5
  %47 = mul nsw i32 %42, %46
  store i32 %47, ptr %5, align 4, !tbaa !5
  %48 = icmp slt i32 %47, 32000
  br label %49

49:                                               ; preds = %41, %37
  %50 = phi i1 [ false, %37 ], [ %48, %41 ]
  br i1 %50, label %52, label %51

51:                                               ; preds = %49
  store i32 5, ptr %3, align 4
  br label %68

52:                                               ; preds = %49
  %53 = load i32, ptr %5, align 4, !tbaa !5
  %54 = sext i32 %53 to i64
  %55 = getelementptr inbounds [32000 x i8], ptr @vis, i64 0, i64 %54
  store i8 1, ptr %55, align 1, !tbaa !9
  %56 = load i32, ptr %2, align 4, !tbaa !5
  %57 = load i32, ptr %4, align 4, !tbaa !5
  %58 = sext i32 %57 to i64
  %59 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %58
  %60 = load i32, ptr %59, align 4, !tbaa !5
  %61 = srem i32 %56, %60
  %62 = icmp eq i32 %61, 0
  br i1 %62, label %63, label %64

63:                                               ; preds = %52
  store i32 5, ptr %3, align 4
  br label %68

64:                                               ; preds = %52
  br label %65

65:                                               ; preds = %64
  %66 = load i32, ptr %4, align 4, !tbaa !5
  %67 = add nsw i32 %66, 1
  store i32 %67, ptr %4, align 4, !tbaa !5
  br label %37, !llvm.loop !13

68:                                               ; preds = %63, %51
  call void @llvm.lifetime.end.p0(i64 4, ptr %5) #5
  call void @llvm.lifetime.end.p0(i64 4, ptr %4) #5
  br label %69

69:                                               ; preds = %68
  br label %70

70:                                               ; preds = %69
  %71 = load i32, ptr %2, align 4, !tbaa !5
  %72 = add nsw i32 %71, 1
  store i32 %72, ptr %2, align 4, !tbaa !5
  br label %20, !llvm.loop !15

73:                                               ; preds = %23
  %74 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str, ptr noundef @n, ptr noundef @m, ptr noundef @p)
  call void @llvm.lifetime.start.p0(i64 4, ptr %6) #5
  store i32 0, ptr %6, align 4, !tbaa !5
  br label %75

75:                                               ; preds = %145, %73
  %76 = load i32, ptr %6, align 4, !tbaa !5
  %77 = load i32, ptr @n, align 4, !tbaa !5
  %78 = icmp sle i32 %76, %77
  br i1 %78, label %80, label %79

79:                                               ; preds = %75
  store i32 8, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %6) #5
  br label %148

80:                                               ; preds = %75
  %81 = load i32, ptr %6, align 4, !tbaa !5
  %82 = sext i32 %81 to i64
  %83 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %82
  %84 = load i32, ptr %6, align 4, !tbaa !5
  %85 = sext i32 %84 to i64
  %86 = getelementptr inbounds [801 x i32], ptr %83, i64 0, i64 %85
  store i32 1, ptr %86, align 4, !tbaa !5
  %87 = load i32, ptr %6, align 4, !tbaa !5
  %88 = sext i32 %87 to i64
  %89 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %88
  %90 = getelementptr inbounds [801 x i32], ptr %89, i64 0, i64 0
  store i32 1, ptr %90, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %7) #5
  store i32 1, ptr %7, align 4, !tbaa !5
  br label %91

91:                                               ; preds = %141, %80
  %92 = load i32, ptr %7, align 4, !tbaa !5
  %93 = load i32, ptr %6, align 4, !tbaa !5
  %94 = icmp slt i32 %92, %93
  br i1 %94, label %96, label %95

95:                                               ; preds = %91
  store i32 11, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %7) #5
  br label %144

96:                                               ; preds = %91
  %97 = load i32, ptr %6, align 4, !tbaa !5
  %98 = sub nsw i32 %97, 1
  %99 = sext i32 %98 to i64
  %100 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %99
  %101 = load i32, ptr %7, align 4, !tbaa !5
  %102 = sub nsw i32 %101, 1
  %103 = sext i32 %102 to i64
  %104 = getelementptr inbounds [801 x i32], ptr %100, i64 0, i64 %103
  %105 = load i32, ptr %104, align 4, !tbaa !5
  %106 = load i32, ptr %6, align 4, !tbaa !5
  %107 = sub nsw i32 %106, 1
  %108 = sext i32 %107 to i64
  %109 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %108
  %110 = load i32, ptr %7, align 4, !tbaa !5
  %111 = sext i32 %110 to i64
  %112 = getelementptr inbounds [801 x i32], ptr %109, i64 0, i64 %111
  %113 = load i32, ptr %112, align 4, !tbaa !5
  %114 = add nsw i32 %105, %113
  %115 = load i32, ptr %6, align 4, !tbaa !5
  %116 = sext i32 %115 to i64
  %117 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %116
  %118 = load i32, ptr %7, align 4, !tbaa !5
  %119 = sext i32 %118 to i64
  %120 = getelementptr inbounds [801 x i32], ptr %117, i64 0, i64 %119
  store i32 %114, ptr %120, align 4, !tbaa !5
  %121 = load i32, ptr %6, align 4, !tbaa !5
  %122 = sext i32 %121 to i64
  %123 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %122
  %124 = load i32, ptr %7, align 4, !tbaa !5
  %125 = sext i32 %124 to i64
  %126 = getelementptr inbounds [801 x i32], ptr %123, i64 0, i64 %125
  %127 = load i32, ptr %126, align 4, !tbaa !5
  %128 = load i32, ptr @p, align 4, !tbaa !5
  %129 = icmp sge i32 %127, %128
  br i1 %129, label %130, label %140

130:                                              ; preds = %96
  %131 = load i32, ptr @p, align 4, !tbaa !5
  %132 = load i32, ptr %6, align 4, !tbaa !5
  %133 = sext i32 %132 to i64
  %134 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %133
  %135 = load i32, ptr %7, align 4, !tbaa !5
  %136 = sext i32 %135 to i64
  %137 = getelementptr inbounds [801 x i32], ptr %134, i64 0, i64 %136
  %138 = load i32, ptr %137, align 4, !tbaa !5
  %139 = sub nsw i32 %138, %131
  store i32 %139, ptr %137, align 4, !tbaa !5
  br label %140

140:                                              ; preds = %130, %96
  br label %141

141:                                              ; preds = %140
  %142 = load i32, ptr %7, align 4, !tbaa !5
  %143 = add nsw i32 %142, 1
  store i32 %143, ptr %7, align 4, !tbaa !5
  br label %91, !llvm.loop !16

144:                                              ; preds = %95
  br label %145

145:                                              ; preds = %144
  %146 = load i32, ptr %6, align 4, !tbaa !5
  %147 = add nsw i32 %146, 1
  store i32 %147, ptr %6, align 4, !tbaa !5
  br label %75, !llvm.loop !17

148:                                              ; preds = %79
  call void @llvm.lifetime.start.p0(i64 4, ptr %8) #5
  %149 = load i32, ptr @p, align 4, !tbaa !5
  store i32 %149, ptr %8, align 4, !tbaa !5
  store i32 0, ptr @cnt, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %9) #5
  store i32 0, ptr %9, align 4, !tbaa !5
  br label %150

150:                                              ; preds = %204, %148
  %151 = load i32, ptr %9, align 4, !tbaa !5
  %152 = load i32, ptr @tot, align 4, !tbaa !5
  %153 = icmp slt i32 %151, %152
  br i1 %153, label %154, label %166

154:                                              ; preds = %150
  %155 = load i32, ptr %9, align 4, !tbaa !5
  %156 = sext i32 %155 to i64
  %157 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %156
  %158 = load i32, ptr %157, align 4, !tbaa !5
  %159 = load i32, ptr %9, align 4, !tbaa !5
  %160 = sext i32 %159 to i64
  %161 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %160
  %162 = load i32, ptr %161, align 4, !tbaa !5
  %163 = mul nsw i32 %158, %162
  %164 = load i32, ptr %8, align 4, !tbaa !5
  %165 = icmp sle i32 %163, %164
  br label %166

166:                                              ; preds = %154, %150
  %167 = phi i1 [ false, %150 ], [ %165, %154 ]
  br i1 %167, label %169, label %168

168:                                              ; preds = %166
  store i32 14, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %9) #5
  br label %207

169:                                              ; preds = %166
  %170 = load i32, ptr %8, align 4, !tbaa !5
  %171 = load i32, ptr %9, align 4, !tbaa !5
  %172 = sext i32 %171 to i64
  %173 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %172
  %174 = load i32, ptr %173, align 4, !tbaa !5
  %175 = srem i32 %170, %174
  %176 = icmp eq i32 %175, 0
  br i1 %176, label %177, label %203

177:                                              ; preds = %169
  %178 = load i32, ptr %9, align 4, !tbaa !5
  %179 = sext i32 %178 to i64
  %180 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %179
  %181 = load i32, ptr %180, align 4, !tbaa !5
  %182 = load i32, ptr @cnt, align 4, !tbaa !5
  %183 = add nsw i32 %182, 1
  store i32 %183, ptr @cnt, align 4, !tbaa !5
  %184 = sext i32 %182 to i64
  %185 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %184
  store i32 %181, ptr %185, align 4, !tbaa !5
  br label %186

186:                                              ; preds = %195, %177
  %187 = load i32, ptr %8, align 4, !tbaa !5
  %188 = load i32, ptr %9, align 4, !tbaa !5
  %189 = sext i32 %188 to i64
  %190 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %189
  %191 = load i32, ptr %190, align 4, !tbaa !5
  %192 = srem i32 %187, %191
  %193 = icmp eq i32 %192, 0
  br i1 %193, label %194, label %202

194:                                              ; preds = %186
  br label %195

195:                                              ; preds = %194
  %196 = load i32, ptr %9, align 4, !tbaa !5
  %197 = sext i32 %196 to i64
  %198 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %197
  %199 = load i32, ptr %198, align 4, !tbaa !5
  %200 = load i32, ptr %8, align 4, !tbaa !5
  %201 = sdiv i32 %200, %199
  store i32 %201, ptr %8, align 4, !tbaa !5
  br label %186, !llvm.loop !18

202:                                              ; preds = %186
  br label %203

203:                                              ; preds = %202, %169
  br label %204

204:                                              ; preds = %203
  %205 = load i32, ptr %9, align 4, !tbaa !5
  %206 = add nsw i32 %205, 1
  store i32 %206, ptr %9, align 4, !tbaa !5
  br label %150, !llvm.loop !19

207:                                              ; preds = %168
  %208 = load i32, ptr %8, align 4, !tbaa !5
  %209 = icmp sgt i32 %208, 1
  br i1 %209, label %210, label %216

210:                                              ; preds = %207
  %211 = load i32, ptr %8, align 4, !tbaa !5
  %212 = load i32, ptr @cnt, align 4, !tbaa !5
  %213 = add nsw i32 %212, 1
  store i32 %213, ptr @cnt, align 4, !tbaa !5
  %214 = sext i32 %212 to i64
  %215 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %214
  store i32 %211, ptr %215, align 4, !tbaa !5
  br label %216

216:                                              ; preds = %210, %207
  store i32 1, ptr @coeff, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %10) #5
  store i32 1, ptr %10, align 4, !tbaa !5
  br label %217

217:                                              ; preds = %298, %216
  %218 = load i32, ptr %10, align 4, !tbaa !5
  %219 = load i32, ptr @n, align 4, !tbaa !5
  %220 = add nsw i32 %219, 1
  %221 = icmp sle i32 %218, %220
  br i1 %221, label %223, label %222

222:                                              ; preds = %217
  store i32 20, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %10) #5
  br label %301

223:                                              ; preds = %217
  call void @llvm.lifetime.start.p0(i64 4, ptr %11) #5
  %224 = load i32, ptr @m, align 4, !tbaa !5
  %225 = load i32, ptr %10, align 4, !tbaa !5
  %226 = add nsw i32 %224, %225
  store i32 %226, ptr %11, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %12) #5
  %227 = load i32, ptr %10, align 4, !tbaa !5
  store i32 %227, ptr %12, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %13) #5
  store i32 0, ptr %13, align 4, !tbaa !5
  br label %228

228:                                              ; preds = %278, %223
  %229 = load i32, ptr %13, align 4, !tbaa !5
  %230 = load i32, ptr @cnt, align 4, !tbaa !5
  %231 = icmp slt i32 %229, %230
  br i1 %231, label %233, label %232

232:                                              ; preds = %228
  store i32 23, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %13) #5
  br label %281

233:                                              ; preds = %228
  br label %234

234:                                              ; preds = %243, %233
  %235 = load i32, ptr %11, align 4, !tbaa !5
  %236 = load i32, ptr %13, align 4, !tbaa !5
  %237 = sext i32 %236 to i64
  %238 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %237
  %239 = load i32, ptr %238, align 4, !tbaa !5
  %240 = srem i32 %235, %239
  %241 = icmp eq i32 %240, 0
  br i1 %241, label %242, label %255

242:                                              ; preds = %234
  br label %243

243:                                              ; preds = %242
  %244 = load i32, ptr %13, align 4, !tbaa !5
  %245 = sext i32 %244 to i64
  %246 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %245
  %247 = load i32, ptr %246, align 4, !tbaa !5
  %248 = add nsw i32 %247, 1
  store i32 %248, ptr %246, align 4, !tbaa !5
  %249 = load i32, ptr %13, align 4, !tbaa !5
  %250 = sext i32 %249 to i64
  %251 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %250
  %252 = load i32, ptr %251, align 4, !tbaa !5
  %253 = load i32, ptr %11, align 4, !tbaa !5
  %254 = sdiv i32 %253, %252
  store i32 %254, ptr %11, align 4, !tbaa !5
  br label %234, !llvm.loop !20

255:                                              ; preds = %234
  br label %256

256:                                              ; preds = %265, %255
  %257 = load i32, ptr %12, align 4, !tbaa !5
  %258 = load i32, ptr %13, align 4, !tbaa !5
  %259 = sext i32 %258 to i64
  %260 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %259
  %261 = load i32, ptr %260, align 4, !tbaa !5
  %262 = srem i32 %257, %261
  %263 = icmp eq i32 %262, 0
  br i1 %263, label %264, label %277

264:                                              ; preds = %256
  br label %265

265:                                              ; preds = %264
  %266 = load i32, ptr %13, align 4, !tbaa !5
  %267 = sext i32 %266 to i64
  %268 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %267
  %269 = load i32, ptr %268, align 4, !tbaa !5
  %270 = add nsw i32 %269, -1
  store i32 %270, ptr %268, align 4, !tbaa !5
  %271 = load i32, ptr %13, align 4, !tbaa !5
  %272 = sext i32 %271 to i64
  %273 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %272
  %274 = load i32, ptr %273, align 4, !tbaa !5
  %275 = load i32, ptr %12, align 4, !tbaa !5
  %276 = sdiv i32 %275, %274
  store i32 %276, ptr %12, align 4, !tbaa !5
  br label %256, !llvm.loop !21

277:                                              ; preds = %256
  br label %278

278:                                              ; preds = %277
  %279 = load i32, ptr %13, align 4, !tbaa !5
  %280 = add nsw i32 %279, 1
  store i32 %280, ptr %13, align 4, !tbaa !5
  br label %228, !llvm.loop !22

281:                                              ; preds = %232
  %282 = load i32, ptr @coeff, align 4, !tbaa !5
  %283 = sext i32 %282 to i64
  %284 = load i32, ptr %11, align 4, !tbaa !5
  %285 = sext i32 %284 to i64
  %286 = mul nsw i64 %283, %285
  %287 = load i32, ptr @p, align 4, !tbaa !5
  %288 = sext i32 %287 to i64
  %289 = srem i64 %286, %288
  %290 = load i32, ptr %12, align 4, !tbaa !5
  %291 = call noundef i32 @_Z7mod_invi(i32 noundef %290)
  %292 = sext i32 %291 to i64
  %293 = mul nsw i64 %289, %292
  %294 = load i32, ptr @p, align 4, !tbaa !5
  %295 = sext i32 %294 to i64
  %296 = srem i64 %293, %295
  %297 = trunc i64 %296 to i32
  store i32 %297, ptr @coeff, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %12) #5
  call void @llvm.lifetime.end.p0(i64 4, ptr %11) #5
  br label %298

298:                                              ; preds = %281
  %299 = load i32, ptr %10, align 4, !tbaa !5
  %300 = add nsw i32 %299, 1
  store i32 %300, ptr %10, align 4, !tbaa !5
  br label %217, !llvm.loop !23

301:                                              ; preds = %222
  call void @llvm.lifetime.start.p0(i64 4, ptr %14) #5
  store i32 0, ptr %14, align 4, !tbaa !5
  br label %302

302:                                              ; preds = %455, %301
  %303 = load i32, ptr %14, align 4, !tbaa !5
  %304 = load i32, ptr @n, align 4, !tbaa !5
  %305 = icmp sle i32 %303, %304
  br i1 %305, label %307, label %306

306:                                              ; preds = %302
  store i32 32, ptr %3, align 4
  br label %458

307:                                              ; preds = %302
  call void @llvm.lifetime.start.p0(i64 4, ptr %15) #5
  %308 = load i32, ptr @n, align 4, !tbaa !5
  %309 = sext i32 %308 to i64
  %310 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %309
  %311 = load i32, ptr %14, align 4, !tbaa !5
  %312 = sext i32 %311 to i64
  %313 = getelementptr inbounds [801 x i32], ptr %310, i64 0, i64 %312
  %314 = load i32, ptr %313, align 4, !tbaa !5
  %315 = sext i32 %314 to i64
  %316 = load i32, ptr @coeff, align 4, !tbaa !5
  %317 = sext i32 %316 to i64
  %318 = mul nsw i64 %315, %317
  %319 = load i32, ptr @p, align 4, !tbaa !5
  %320 = sext i32 %319 to i64
  %321 = srem i64 %318, %320
  %322 = trunc i64 %321 to i32
  store i32 %322, ptr %15, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %16) #5
  store i32 0, ptr %16, align 4, !tbaa !5
  br label %323

323:                                              ; preds = %353, %307
  %324 = load i32, ptr %16, align 4, !tbaa !5
  %325 = load i32, ptr @cnt, align 4, !tbaa !5
  %326 = icmp slt i32 %324, %325
  br i1 %326, label %328, label %327

327:                                              ; preds = %323
  store i32 35, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %16) #5
  br label %356

328:                                              ; preds = %323
  %329 = load i32, ptr %16, align 4, !tbaa !5
  %330 = sext i32 %329 to i64
  %331 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %330
  %332 = load i32, ptr %331, align 4, !tbaa !5
  %333 = icmp ne i32 %332, 0
  br i1 %333, label %334, label %352

334:                                              ; preds = %328
  %335 = load i32, ptr %15, align 4, !tbaa !5
  %336 = sext i32 %335 to i64
  %337 = load i32, ptr %16, align 4, !tbaa !5
  %338 = sext i32 %337 to i64
  %339 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %338
  %340 = load i32, ptr %339, align 4, !tbaa !5
  %341 = load i32, ptr %16, align 4, !tbaa !5
  %342 = sext i32 %341 to i64
  %343 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %342
  %344 = load i32, ptr %343, align 4, !tbaa !5
  %345 = call noundef i32 @_Z7mod_powii(i32 noundef %340, i32 noundef %344)
  %346 = sext i32 %345 to i64
  %347 = mul nsw i64 %336, %346
  %348 = load i32, ptr @p, align 4, !tbaa !5
  %349 = sext i32 %348 to i64
  %350 = srem i64 %347, %349
  %351 = trunc i64 %350 to i32
  store i32 %351, ptr %15, align 4, !tbaa !5
  br label %352

352:                                              ; preds = %334, %328
  br label %353

353:                                              ; preds = %352
  %354 = load i32, ptr %16, align 4, !tbaa !5
  %355 = add nsw i32 %354, 1
  store i32 %355, ptr %16, align 4, !tbaa !5
  br label %323, !llvm.loop !24

356:                                              ; preds = %327
  %357 = load i32, ptr %15, align 4, !tbaa !5
  %358 = load i32, ptr @ans, align 4, !tbaa !5
  %359 = add nsw i32 %358, %357
  store i32 %359, ptr @ans, align 4, !tbaa !5
  %360 = load i32, ptr @ans, align 4, !tbaa !5
  %361 = load i32, ptr @p, align 4, !tbaa !5
  %362 = icmp sge i32 %360, %361
  br i1 %362, label %363, label %367

363:                                              ; preds = %356
  %364 = load i32, ptr @p, align 4, !tbaa !5
  %365 = load i32, ptr @ans, align 4, !tbaa !5
  %366 = sub nsw i32 %365, %364
  store i32 %366, ptr @ans, align 4, !tbaa !5
  br label %367

367:                                              ; preds = %363, %356
  %368 = load i32, ptr %14, align 4, !tbaa !5
  %369 = load i32, ptr @m, align 4, !tbaa !5
  %370 = icmp eq i32 %368, %369
  br i1 %370, label %371, label %372

371:                                              ; preds = %367
  store i32 32, ptr %3, align 4
  br label %452

372:                                              ; preds = %367
  call void @llvm.lifetime.start.p0(i64 4, ptr %17) #5
  %373 = load i32, ptr @m, align 4, !tbaa !5
  %374 = load i32, ptr %14, align 4, !tbaa !5
  %375 = sub nsw i32 %373, %374
  store i32 %375, ptr %17, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %18) #5
  %376 = load i32, ptr @n, align 4, !tbaa !5
  %377 = add nsw i32 %376, 1
  %378 = load i32, ptr @m, align 4, !tbaa !5
  %379 = add nsw i32 %377, %378
  %380 = load i32, ptr %14, align 4, !tbaa !5
  %381 = sub nsw i32 %379, %380
  store i32 %381, ptr %18, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %19) #5
  store i32 0, ptr %19, align 4, !tbaa !5
  br label %382

382:                                              ; preds = %432, %372
  %383 = load i32, ptr %19, align 4, !tbaa !5
  %384 = load i32, ptr @cnt, align 4, !tbaa !5
  %385 = icmp slt i32 %383, %384
  br i1 %385, label %387, label %386

386:                                              ; preds = %382
  store i32 38, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %19) #5
  br label %435

387:                                              ; preds = %382
  br label %388

388:                                              ; preds = %397, %387
  %389 = load i32, ptr %17, align 4, !tbaa !5
  %390 = load i32, ptr %19, align 4, !tbaa !5
  %391 = sext i32 %390 to i64
  %392 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %391
  %393 = load i32, ptr %392, align 4, !tbaa !5
  %394 = srem i32 %389, %393
  %395 = icmp eq i32 %394, 0
  br i1 %395, label %396, label %409

396:                                              ; preds = %388
  br label %397

397:                                              ; preds = %396
  %398 = load i32, ptr %19, align 4, !tbaa !5
  %399 = sext i32 %398 to i64
  %400 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %399
  %401 = load i32, ptr %400, align 4, !tbaa !5
  %402 = add nsw i32 %401, 1
  store i32 %402, ptr %400, align 4, !tbaa !5
  %403 = load i32, ptr %19, align 4, !tbaa !5
  %404 = sext i32 %403 to i64
  %405 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %404
  %406 = load i32, ptr %405, align 4, !tbaa !5
  %407 = load i32, ptr %17, align 4, !tbaa !5
  %408 = sdiv i32 %407, %406
  store i32 %408, ptr %17, align 4, !tbaa !5
  br label %388, !llvm.loop !25

409:                                              ; preds = %388
  br label %410

410:                                              ; preds = %419, %409
  %411 = load i32, ptr %18, align 4, !tbaa !5
  %412 = load i32, ptr %19, align 4, !tbaa !5
  %413 = sext i32 %412 to i64
  %414 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %413
  %415 = load i32, ptr %414, align 4, !tbaa !5
  %416 = srem i32 %411, %415
  %417 = icmp eq i32 %416, 0
  br i1 %417, label %418, label %431

418:                                              ; preds = %410
  br label %419

419:                                              ; preds = %418
  %420 = load i32, ptr %19, align 4, !tbaa !5
  %421 = sext i32 %420 to i64
  %422 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %421
  %423 = load i32, ptr %422, align 4, !tbaa !5
  %424 = add nsw i32 %423, -1
  store i32 %424, ptr %422, align 4, !tbaa !5
  %425 = load i32, ptr %19, align 4, !tbaa !5
  %426 = sext i32 %425 to i64
  %427 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %426
  %428 = load i32, ptr %427, align 4, !tbaa !5
  %429 = load i32, ptr %18, align 4, !tbaa !5
  %430 = sdiv i32 %429, %428
  store i32 %430, ptr %18, align 4, !tbaa !5
  br label %410, !llvm.loop !26

431:                                              ; preds = %410
  br label %432

432:                                              ; preds = %431
  %433 = load i32, ptr %19, align 4, !tbaa !5
  %434 = add nsw i32 %433, 1
  store i32 %434, ptr %19, align 4, !tbaa !5
  br label %382, !llvm.loop !27

435:                                              ; preds = %386
  %436 = load i32, ptr @coeff, align 4, !tbaa !5
  %437 = sext i32 %436 to i64
  %438 = load i32, ptr %17, align 4, !tbaa !5
  %439 = sext i32 %438 to i64
  %440 = mul nsw i64 %437, %439
  %441 = load i32, ptr @p, align 4, !tbaa !5
  %442 = sext i32 %441 to i64
  %443 = srem i64 %440, %442
  %444 = load i32, ptr %18, align 4, !tbaa !5
  %445 = call noundef i32 @_Z7mod_invi(i32 noundef %444)
  %446 = sext i32 %445 to i64
  %447 = mul nsw i64 %443, %446
  %448 = load i32, ptr @p, align 4, !tbaa !5
  %449 = sext i32 %448 to i64
  %450 = srem i64 %447, %449
  %451 = trunc i64 %450 to i32
  store i32 %451, ptr @coeff, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %18) #5
  call void @llvm.lifetime.end.p0(i64 4, ptr %17) #5
  store i32 0, ptr %3, align 4
  br label %452

452:                                              ; preds = %435, %371
  call void @llvm.lifetime.end.p0(i64 4, ptr %15) #5
  %453 = load i32, ptr %3, align 4
  switch i32 %453, label %458 [
    i32 0, label %454
  ]

454:                                              ; preds = %452
  br label %455

455:                                              ; preds = %454
  %456 = load i32, ptr %14, align 4, !tbaa !5
  %457 = add nsw i32 %456, 1
  store i32 %457, ptr %14, align 4, !tbaa !5
  br label %302, !llvm.loop !28

458:                                              ; preds = %452, %306
  call void @llvm.lifetime.end.p0(i64 4, ptr %14) #5
  br label %459

459:                                              ; preds = %458
  %460 = load i32, ptr @ans, align 4, !tbaa !5
  %461 = call i32 (ptr, ...) @printf(ptr noundef @.str.1, i32 noundef %460)
  store i32 0, ptr %1, align 4
  store i32 1, ptr %3, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %8) #5
  %462 = load i32, ptr %1, align 4
  ret i32 %462
}

declare i32 @__isoc99_scanf(ptr noundef, ...) #4

declare i32 @printf(ptr noundef, ...) #4

attributes #0 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { mustprogress norecurse uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #4 = { "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #5 = { nounwind }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"bool", !7, i64 0}
!11 = !{i8 0, i8 2}
!12 = !{}
!13 = distinct !{!13, !14}
!14 = !{!"llvm.loop.mustprogress"}
!15 = distinct !{!15, !14}
!16 = distinct !{!16, !14}
!17 = distinct !{!17, !14}
!18 = distinct !{!18, !14}
!19 = distinct !{!19, !14}
!20 = distinct !{!20, !14}
!21 = distinct !{!21, !14}
!22 = distinct !{!22, !14}
!23 = distinct !{!23, !14}
!24 = distinct !{!24, !14}
!25 = distinct !{!25, !14}
!26 = distinct !{!26, !14}
!27 = distinct !{!27, !14}
!28 = distinct !{!28, !14}


; Optimized IR (opt -passes='default<O3>'):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@n = external dso_local global i32, align 4
@m = external dso_local global i32, align 4
@p = external dso_local global i32, align 4
@c = external dso_local local_unnamed_addr global [801 x [801 x i32]], align 16
@ans = external dso_local local_unnamed_addr global i32, align 4
@tot = external dso_local local_unnamed_addr global i32, align 4
@prime = external dso_local local_unnamed_addr global [32000 x i32], align 16
@cnt = external dso_local local_unnamed_addr global i32, align 4
@fact = external dso_local local_unnamed_addr global [10 x i32], align 16
@exp = external dso_local local_unnamed_addr global [10 x i32], align 16
@coeff = external dso_local local_unnamed_addr global i32, align 4
@vis = external dso_local local_unnamed_addr global [32000 x i8], align 16
@.str = external hidden unnamed_addr constant [7 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [4 x i8], align 1

; Function Attrs: mustprogress uwtable
declare dso_local noundef i32 @_Z7mod_invi(i32 noundef) local_unnamed_addr #0

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef i32 @_Z7mod_powii(i32 noundef, i32 noundef) local_unnamed_addr #1

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() local_unnamed_addr #2 {
  %tot.promoted = load i32, ptr @tot, align 4, !tbaa !5
  br label %5

1:                                                ; preds = %.critedge
  %2 = tail call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull @n, ptr noundef nonnull @m, ptr noundef nonnull @p)
  %3 = load i32, ptr @n, align 4, !tbaa !5
  %.not144 = icmp slt i32 %3, 0
  %.pre254 = load i32, ptr @p, align 4
  br i1 %.not144, label %._crit_edge148, label %.lr.ph147

.lr.ph147:                                        ; preds = %1
  %4 = add nuw i32 %3, 1
  %wide.trip.count232 = zext i32 %4 to i64
  %broadcast.splatinsert = insertelement <4 x i32> poison, i32 %.pre254, i64 0
  %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, <4 x i32> poison, <4 x i32> zeroinitializer
  br label %32

5:                                                ; preds = %0, %.critedge
  %indvars.iv222 = phi i64 [ 2, %0 ], [ %indvars.iv.next223, %.critedge ]
  %6 = phi i32 [ %tot.promoted, %0 ], [ %16, %.critedge ]
  %7 = getelementptr inbounds [32000 x i8], ptr @vis, i64 0, i64 %indvars.iv222
  %8 = load i8, ptr %7, align 1, !tbaa !9, !range !11, !noundef !12
  %9 = trunc nuw i8 %8 to i1
  br i1 %9, label %15, label %10

10:                                               ; preds = %5
  %11 = add nsw i32 %6, 1
  store i32 %11, ptr @tot, align 4, !tbaa !5
  %12 = sext i32 %6 to i64
  %13 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %12
  %14 = trunc nuw nsw i64 %indvars.iv222 to i32
  store i32 %14, ptr %13, align 4, !tbaa !5
  br label %15

15:                                               ; preds = %10, %5
  %16 = phi i32 [ %11, %10 ], [ %6, %5 ]
  %17 = icmp sgt i32 %16, 0
  br i1 %17, label %.lr.ph.preheader, label %.critedge

.lr.ph.preheader:                                 ; preds = %15
  %18 = zext nneg i32 %16 to i64
  %19 = trunc nuw nsw i64 %indvars.iv222 to i32
  br label %.lr.ph

.lr.ph:                                           ; preds = %.lr.ph.preheader, %24
  %indvars.iv = phi i64 [ 0, %.lr.ph.preheader ], [ %indvars.iv.next, %24 ]
  %20 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %indvars.iv
  %21 = load i32, ptr %20, align 4, !tbaa !5
  %22 = mul nsw i32 %21, %19
  %23 = icmp slt i32 %22, 32000
  br i1 %23, label %24, label %.critedge

24:                                               ; preds = %.lr.ph
  %25 = sext i32 %22 to i64
  %26 = getelementptr inbounds [32000 x i8], ptr @vis, i64 0, i64 %25
  store i8 1, ptr %26, align 1, !tbaa !9
  %27 = srem i32 %19, %21
  %28 = icmp ne i32 %27, 0
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %29 = icmp ult i64 %indvars.iv.next, %18
  %or.cond = select i1 %28, i1 %29, i1 false
  br i1 %or.cond, label %.lr.ph, label %.critedge, !llvm.loop !13

.critedge:                                        ; preds = %.lr.ph, %24, %15
  %indvars.iv.next223 = add nuw nsw i64 %indvars.iv222, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next223, 32000
  br i1 %exitcond.not, label %1, label %5, !llvm.loop !15

._crit_edge148:                                   ; preds = %._crit_edge, %1
  store i32 0, ptr @cnt, align 4, !tbaa !5
  %30 = load i32, ptr @tot, align 4, !tbaa !5
  %31 = icmp sgt i32 %30, 0
  br i1 %31, label %.lr.ph155.preheader, label %.critedge2

.lr.ph155.preheader:                              ; preds = %._crit_edge148
  %wide.trip.count = zext nneg i32 %30 to i64
  br label %.lr.ph155

32:                                               ; preds = %.lr.ph147, %._crit_edge
  %indvars.iv229 = phi i64 [ 0, %.lr.ph147 ], [ %indvars.iv.next230, %._crit_edge ]
  %33 = add nsw i64 %indvars.iv229, -1
  %34 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %indvars.iv229
  %35 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %indvars.iv229, i64 %indvars.iv229
  store i32 1, ptr %35, align 4, !tbaa !5
  store i32 1, ptr %34, align 4, !tbaa !5
  %36 = icmp ugt i64 %indvars.iv229, 1
  br i1 %36, label %.lr.ph143, label %._crit_edge

.lr.ph143:                                        ; preds = %32
  %37 = add nsw i64 %indvars.iv229, -1
  %.phi.trans.insert = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %37, i64 0
  %.pre = load i32, ptr %.phi.trans.insert, align 4, !tbaa !5
  %min.iters.check = icmp ult i64 %indvars.iv229, 5
  br i1 %min.iters.check, label %scalar.ph.preheader, label %vector.ph

scalar.ph.preheader:                              ; preds = %middle.block, %.lr.ph143
  %.ph302 = phi i32 [ %.pre, %.lr.ph143 ], [ %vector.recur.extract, %middle.block ]
  %indvars.iv225.ph = phi i64 [ 1, %.lr.ph143 ], [ %ind.end, %middle.block ]
  br label %scalar.ph

vector.ph:                                        ; preds = %.lr.ph143
  %n.vec = and i64 %33, -4
  %ind.end = or disjoint i64 %n.vec, 1
  %vector.recur.init = insertelement <4 x i32> poison, i32 %.pre, i64 3
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %vector.recur = phi <4 x i32> [ %vector.recur.init, %vector.ph ], [ %wide.load, %vector.body ]
  %offset.idx = or disjoint i64 %index, 1
  %38 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %37, i64 %offset.idx
  %wide.load = load <4 x i32>, ptr %38, align 4, !tbaa !5
  %39 = shufflevector <4 x i32> %vector.recur, <4 x i32> %wide.load, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
  %40 = add nsw <4 x i32> %wide.load, %39
  %41 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %indvars.iv229, i64 %offset.idx
  %42 = icmp slt <4 x i32> %40, %broadcast.splat
  %43 = select <4 x i1> %42, <4 x i32> zeroinitializer, <4 x i32> %broadcast.splat
  %44 = sub nsw <4 x i32> %40, %43
  store <4 x i32> %44, ptr %41, align 4, !tbaa !5
  %index.next = add nuw i64 %index, 4
  %45 = icmp eq i64 %index.next, %n.vec
  br i1 %45, label %middle.block, label %vector.body, !llvm.loop !16

middle.block:                                     ; preds = %vector.body
  %vector.recur.extract = extractelement <4 x i32> %wide.load, i64 3
  %cmp.n = icmp eq i64 %33, %n.vec
  br i1 %cmp.n, label %._crit_edge, label %scalar.ph.preheader

._crit_edge:                                      ; preds = %scalar.ph, %middle.block, %32
  %indvars.iv.next230 = add nuw nsw i64 %indvars.iv229, 1
  %exitcond233.not = icmp eq i64 %indvars.iv.next230, %wide.trip.count232
  br i1 %exitcond233.not, label %._crit_edge148, label %32, !llvm.loop !19

scalar.ph:                                        ; preds = %scalar.ph.preheader, %scalar.ph
  %46 = phi i32 [ %48, %scalar.ph ], [ %.ph302, %scalar.ph.preheader ]
  %indvars.iv225 = phi i64 [ %indvars.iv.next226, %scalar.ph ], [ %indvars.iv225.ph, %scalar.ph.preheader ]
  %47 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %37, i64 %indvars.iv225
  %48 = load i32, ptr %47, align 4, !tbaa !5
  %49 = add nsw i32 %48, %46
  %50 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %indvars.iv229, i64 %indvars.iv225
  %.not127 = icmp slt i32 %49, %.pre254
  %51 = select i1 %.not127, i32 0, i32 %.pre254
  %spec.select = sub nsw i32 %49, %51
  store i32 %spec.select, ptr %50, align 4, !tbaa !5
  %indvars.iv.next226 = add nuw nsw i64 %indvars.iv225, 1
  %exitcond228.not = icmp eq i64 %indvars.iv.next226, %indvars.iv229
  br i1 %exitcond228.not, label %._crit_edge, label %scalar.ph, !llvm.loop !20

.lr.ph155:                                        ; preds = %.lr.ph155.preheader, %.loopexit
  %52 = phi i32 [ 0, %.lr.ph155.preheader ], [ %68, %.loopexit ]
  %indvars.iv234 = phi i64 [ 0, %.lr.ph155.preheader ], [ %indvars.iv.next235, %.loopexit ]
  %.0106152 = phi i32 [ %.pre254, %.lr.ph155.preheader ], [ %.2, %.loopexit ]
  %53 = phi i32 [ 0, %.lr.ph155.preheader ], [ %69, %.loopexit ]
  %54 = getelementptr inbounds [32000 x i32], ptr @prime, i64 0, i64 %indvars.iv234
  %55 = load i32, ptr %54, align 4, !tbaa !5
  %56 = mul nsw i32 %55, %55
  %.not121 = icmp sgt i32 %56, %.0106152
  br i1 %.not121, label %.critedge2, label %59

.critedge2:                                       ; preds = %.lr.ph155, %.loopexit, %._crit_edge148
  %57 = phi i32 [ 0, %._crit_edge148 ], [ %68, %.loopexit ], [ %52, %.lr.ph155 ]
  %.0106.lcssa = phi i32 [ %.pre254, %._crit_edge148 ], [ %.2, %.loopexit ], [ %.0106152, %.lr.ph155 ]
  %58 = icmp sgt i32 %.0106.lcssa, 1
  br i1 %58, label %70, label %74

59:                                               ; preds = %.lr.ph155
  %60 = srem i32 %.0106152, %55
  %61 = icmp eq i32 %60, 0
  br i1 %61, label %.lr.ph151.preheader, label %.loopexit

.lr.ph151.preheader:                              ; preds = %59
  %62 = add nsw i32 %53, 1
  store i32 %62, ptr @cnt, align 4, !tbaa !5
  %63 = sext i32 %53 to i64
  %64 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %63
  store i32 %55, ptr %64, align 4, !tbaa !5
  br label %.lr.ph151

.lr.ph151:                                        ; preds = %.lr.ph151.preheader, %.lr.ph151
  %.1107149 = phi i32 [ %65, %.lr.ph151 ], [ %.0106152, %.lr.ph151.preheader ]
  %65 = sdiv i32 %.1107149, %55
  %66 = srem i32 %65, %55
  %67 = icmp eq i32 %66, 0
  br i1 %67, label %.lr.ph151, label %.loopexit, !llvm.loop !21

.loopexit:                                        ; preds = %.lr.ph151, %59
  %68 = phi i32 [ %52, %59 ], [ %62, %.lr.ph151 ]
  %69 = phi i32 [ %53, %59 ], [ %62, %.lr.ph151 ]
  %.2 = phi i32 [ %.0106152, %59 ], [ %65, %.lr.ph151 ]
  %indvars.iv.next235 = add nuw nsw i64 %indvars.iv234, 1
  %exitcond237.not = icmp eq i64 %indvars.iv.next235, %wide.trip.count
  br i1 %exitcond237.not, label %.critedge2, label %.lr.ph155, !llvm.loop !22

70:                                               ; preds = %.critedge2
  %71 = add nsw i32 %57, 1
  store i32 %71, ptr @cnt, align 4, !tbaa !5
  %72 = sext i32 %57 to i64
  %73 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %72
  store i32 %.0106.lcssa, ptr %73, align 4, !tbaa !5
  br label %74

74:                                               ; preds = %70, %.critedge2
  store i32 1, ptr @coeff, align 4, !tbaa !5
  br i1 %.not144, label %.critedge129, label %.lr.ph180

.preheader131:                                    ; preds = %._crit_edge174
  %.not123207 = icmp slt i32 %99, 0
  br i1 %.not123207, label %.critedge129, label %.lr.ph209

.lr.ph180:                                        ; preds = %74, %._crit_edge174
  %75 = phi i32 [ %94, %._crit_edge174 ], [ %.pre254, %74 ]
  %76 = phi i64 [ %96, %._crit_edge174 ], [ 1, %74 ]
  %.0104178 = phi i32 [ %98, %._crit_edge174 ], [ 1, %74 ]
  %77 = load i32, ptr @m, align 4, !tbaa !5
  %78 = add nsw i32 %77, %.0104178
  %79 = load i32, ptr @cnt, align 4, !tbaa !5
  %80 = icmp sgt i32 %79, 0
  br i1 %80, label %.preheader133.preheader, label %._crit_edge174

.preheader133.preheader:                          ; preds = %.lr.ph180
  %wide.trip.count241 = zext nneg i32 %79 to i64
  br label %.preheader133

.preheader133:                                    ; preds = %.preheader133.preheader, %115
  %indvars.iv238 = phi i64 [ 0, %.preheader133.preheader ], [ %indvars.iv.next239, %115 ]
  %.0100172 = phi i32 [ %.0104178, %.preheader133.preheader ], [ %.1101.lcssa, %115 ]
  %.0102171 = phi i32 [ %78, %.preheader133.preheader ], [ %.1103.lcssa, %115 ]
  %81 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %indvars.iv238
  %82 = load i32, ptr %81, align 4, !tbaa !5
  %83 = srem i32 %.0102171, %82
  %84 = icmp eq i32 %83, 0
  br i1 %84, label %.lr.ph160, label %.preheader132

.lr.ph160:                                        ; preds = %.preheader133
  %85 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %indvars.iv238
  %.promoted = load i32, ptr %85, align 4, !tbaa !5
  br label %103

._crit_edge174:                                   ; preds = %115, %.lr.ph180
  %.0102.lcssa = phi i32 [ %78, %.lr.ph180 ], [ %.1103.lcssa, %115 ]
  %.0100.lcssa = phi i32 [ %.0104178, %.lr.ph180 ], [ %.1101.lcssa, %115 ]
  %sext = shl i64 %76, 32
  %86 = ashr exact i64 %sext, 32
  %87 = sext i32 %.0102.lcssa to i64
  %88 = mul nsw i64 %86, %87
  %89 = sext i32 %75 to i64
  %90 = srem i64 %88, %89
  %91 = tail call noundef i32 @_Z7mod_invi(i32 noundef %.0100.lcssa)
  %92 = sext i32 %91 to i64
  %93 = mul nsw i64 %90, %92
  %94 = load i32, ptr @p, align 4, !tbaa !5
  %95 = sext i32 %94 to i64
  %96 = srem i64 %93, %95
  %97 = trunc nsw i64 %96 to i32
  store i32 %97, ptr @coeff, align 4, !tbaa !5
  %98 = add nuw nsw i32 %.0104178, 1
  %99 = load i32, ptr @n, align 4, !tbaa !5
  %.not122 = icmp sgt i32 %.0104178, %99
  br i1 %.not122, label %.preheader131, label %.lr.ph180, !llvm.loop !23

..preheader132_crit_edge:                         ; preds = %103
  store i32 %105, ptr %85, align 4, !tbaa !5
  br label %.preheader132

.preheader132:                                    ; preds = %..preheader132_crit_edge, %.preheader133
  %.1103.lcssa = phi i32 [ %106, %..preheader132_crit_edge ], [ %.0102171, %.preheader133 ]
  %100 = srem i32 %.0100172, %82
  %101 = icmp eq i32 %100, 0
  br i1 %101, label %.lr.ph166, label %115

.lr.ph166:                                        ; preds = %.preheader132
  %102 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %indvars.iv238
  %.promoted169 = load i32, ptr %102, align 4, !tbaa !5
  br label %109

103:                                              ; preds = %.lr.ph160, %103
  %104 = phi i32 [ %.promoted, %.lr.ph160 ], [ %105, %103 ]
  %.1103159 = phi i32 [ %.0102171, %.lr.ph160 ], [ %106, %103 ]
  %105 = add nsw i32 %104, 1
  %106 = sdiv i32 %.1103159, %82
  %107 = srem i32 %106, %82
  %108 = icmp eq i32 %107, 0
  br i1 %108, label %103, label %..preheader132_crit_edge, !llvm.loop !24

109:                                              ; preds = %.lr.ph166, %109
  %110 = phi i32 [ %.promoted169, %.lr.ph166 ], [ %111, %109 ]
  %.1101165 = phi i32 [ %.0100172, %.lr.ph166 ], [ %112, %109 ]
  %111 = add nsw i32 %110, -1
  %112 = sdiv i32 %.1101165, %82
  %113 = srem i32 %112, %82
  %114 = icmp eq i32 %113, 0
  br i1 %114, label %109, label %._crit_edge167, !llvm.loop !25

._crit_edge167:                                   ; preds = %109
  store i32 %111, ptr %102, align 4, !tbaa !5
  br label %115

115:                                              ; preds = %._crit_edge167, %.preheader132
  %.1101.lcssa = phi i32 [ %112, %._crit_edge167 ], [ %.0100172, %.preheader132 ]
  %indvars.iv.next239 = add nuw nsw i64 %indvars.iv238, 1
  %exitcond242.not = icmp eq i64 %indvars.iv.next239, %wide.trip.count241
  br i1 %exitcond242.not, label %._crit_edge174, label %.preheader133, !llvm.loop !26

.lr.ph209:                                        ; preds = %.preheader131, %._crit_edge204
  %116 = phi i32 [ %193, %._crit_edge204 ], [ %94, %.preheader131 ]
  %117 = phi i64 [ %195, %._crit_edge204 ], [ %96, %.preheader131 ]
  %indvars.iv251 = phi i64 [ %indvars.iv.next252, %._crit_edge204 ], [ 0, %.preheader131 ]
  %118 = phi i32 [ %197, %._crit_edge204 ], [ %99, %.preheader131 ]
  %119 = sext i32 %118 to i64
  %120 = getelementptr inbounds [801 x [801 x i32]], ptr @c, i64 0, i64 %119, i64 %indvars.iv251
  %121 = load i32, ptr %120, align 4, !tbaa !5
  %122 = sext i32 %121 to i64
  %sext256 = shl i64 %117, 32
  %123 = ashr exact i64 %sext256, 32
  %124 = mul nsw i64 %123, %122
  %125 = sext i32 %116 to i64
  %126 = srem i64 %124, %125
  %127 = trunc nsw i64 %126 to i32
  %128 = load i32, ptr @cnt, align 4, !tbaa !5
  %129 = icmp sgt i32 %128, 0
  br i1 %129, label %.lr.ph184, label %._crit_edge185

._crit_edge185:                                   ; preds = %151, %.lr.ph209
  %130 = phi i32 [ %116, %.lr.ph209 ], [ %152, %151 ]
  %.096.lcssa = phi i32 [ %127, %.lr.ph209 ], [ %.197, %151 ]
  %.lcssa = phi i32 [ %128, %.lr.ph209 ], [ %153, %151 ]
  %131 = load i32, ptr @ans, align 4, !tbaa !5
  %132 = add nsw i32 %131, %.096.lcssa
  %.not124 = icmp slt i32 %132, %130
  %133 = select i1 %.not124, i32 0, i32 %130
  %spec.select273 = sub nsw i32 %132, %133
  store i32 %spec.select273, ptr @ans, align 4, !tbaa !5
  %134 = load i32, ptr @m, align 4, !tbaa !5
  %135 = zext i32 %134 to i64
  %.not125 = icmp eq i64 %indvars.iv251, %135
  br i1 %.not125, label %.critedge129, label %156

.lr.ph184:                                        ; preds = %.lr.ph209, %151
  %136 = phi i32 [ %152, %151 ], [ %116, %.lr.ph209 ]
  %137 = phi i32 [ %153, %151 ], [ %128, %.lr.ph209 ]
  %indvars.iv243 = phi i64 [ %indvars.iv.next244, %151 ], [ 0, %.lr.ph209 ]
  %.096181 = phi i32 [ %.197, %151 ], [ %127, %.lr.ph209 ]
  %138 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %indvars.iv243
  %139 = load i32, ptr %138, align 4, !tbaa !5
  %.not126 = icmp eq i32 %139, 0
  br i1 %.not126, label %151, label %140

140:                                              ; preds = %.lr.ph184
  %141 = sext i32 %.096181 to i64
  %142 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %indvars.iv243
  %143 = load i32, ptr %142, align 4, !tbaa !5
  %144 = tail call noundef i32 @_Z7mod_powii(i32 noundef %143, i32 noundef %139)
  %145 = sext i32 %144 to i64
  %146 = mul nsw i64 %145, %141
  %147 = load i32, ptr @p, align 4, !tbaa !5
  %148 = sext i32 %147 to i64
  %149 = srem i64 %146, %148
  %150 = trunc nsw i64 %149 to i32
  %.pre255 = load i32, ptr @cnt, align 4, !tbaa !5
  br label %151

151:                                              ; preds = %.lr.ph184, %140
  %152 = phi i32 [ %147, %140 ], [ %136, %.lr.ph184 ]
  %153 = phi i32 [ %.pre255, %140 ], [ %137, %.lr.ph184 ]
  %.197 = phi i32 [ %150, %140 ], [ %.096181, %.lr.ph184 ]
  %indvars.iv.next244 = add nuw nsw i64 %indvars.iv243, 1
  %154 = sext i32 %153 to i64
  %155 = icmp slt i64 %indvars.iv.next244, %154
  br i1 %155, label %.lr.ph184, label %._crit_edge185, !llvm.loop !27

156:                                              ; preds = %._crit_edge185
  %157 = trunc nuw nsw i64 %indvars.iv251 to i32
  %158 = sub i32 %134, %157
  %159 = load i32, ptr @n, align 4, !tbaa !5
  %160 = add i32 %158, 1
  %161 = add i32 %160, %159
  %162 = icmp sgt i32 %.lcssa, 0
  br i1 %162, label %.preheader130.preheader, label %._crit_edge204

.preheader130.preheader:                          ; preds = %156
  %wide.trip.count249 = zext nneg i32 %.lcssa to i64
  br label %.preheader130

.preheader130:                                    ; preds = %.preheader130.preheader, %183
  %indvars.iv246 = phi i64 [ 0, %.preheader130.preheader ], [ %indvars.iv.next247, %183 ]
  %.092202 = phi i32 [ %161, %.preheader130.preheader ], [ %.1.lcssa, %183 ]
  %.093201 = phi i32 [ %158, %.preheader130.preheader ], [ %.194.lcssa, %183 ]
  %163 = getelementptr inbounds [10 x i32], ptr @fact, i64 0, i64 %indvars.iv246
  %164 = load i32, ptr %163, align 4, !tbaa !5
  %165 = srem i32 %.093201, %164
  %166 = icmp eq i32 %165, 0
  br i1 %166, label %.lr.ph189, label %.preheader

.lr.ph189:                                        ; preds = %.preheader130
  %167 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %indvars.iv246
  %.promoted193 = load i32, ptr %167, align 4, !tbaa !5
  br label %171

..preheader_crit_edge:                            ; preds = %171
  store i32 %173, ptr %167, align 4, !tbaa !5
  br label %.preheader

.preheader:                                       ; preds = %..preheader_crit_edge, %.preheader130
  %.194.lcssa = phi i32 [ %174, %..preheader_crit_edge ], [ %.093201, %.preheader130 ]
  %168 = srem i32 %.092202, %164
  %169 = icmp eq i32 %168, 0
  br i1 %169, label %.lr.ph196, label %183

.lr.ph196:                                        ; preds = %.preheader
  %170 = getelementptr inbounds [10 x i32], ptr @exp, i64 0, i64 %indvars.iv246
  %.promoted199 = load i32, ptr %170, align 4, !tbaa !5
  br label %177

171:                                              ; preds = %.lr.ph189, %171
  %172 = phi i32 [ %.promoted193, %.lr.ph189 ], [ %173, %171 ]
  %.194188 = phi i32 [ %.093201, %.lr.ph189 ], [ %174, %171 ]
  %173 = add nsw i32 %172, 1
  %174 = sdiv i32 %.194188, %164
  %175 = srem i32 %174, %164
  %176 = icmp eq i32 %175, 0
  br i1 %176, label %171, label %..preheader_crit_edge, !llvm.loop !28

177:                                              ; preds = %.lr.ph196, %177
  %178 = phi i32 [ %.promoted199, %.lr.ph196 ], [ %179, %177 ]
  %.1195 = phi i32 [ %.092202, %.lr.ph196 ], [ %180, %177 ]
  %179 = add nsw i32 %178, -1
  %180 = sdiv i32 %.1195, %164
  %181 = srem i32 %180, %164
  %182 = icmp eq i32 %181, 0
  br i1 %182, label %177, label %._crit_edge197, !llvm.loop !29

._crit_edge197:                                   ; preds = %177
  store i32 %179, ptr %170, align 4, !tbaa !5
  br label %183

183:                                              ; preds = %._crit_edge197, %.preheader
  %.1.lcssa = phi i32 [ %180, %._crit_edge197 ], [ %.092202, %.preheader ]
  %indvars.iv.next247 = add nuw nsw i64 %indvars.iv246, 1
  %exitcond250.not = icmp eq i64 %indvars.iv.next247, %wide.trip.count249
  br i1 %exitcond250.not, label %._crit_edge204, label %.preheader130, !llvm.loop !30

._crit_edge204:                                   ; preds = %183, %156
  %.093.lcssa = phi i32 [ %158, %156 ], [ %.194.lcssa, %183 ]
  %.092.lcssa = phi i32 [ %161, %156 ], [ %.1.lcssa, %183 ]
  %184 = load i32, ptr @coeff, align 4, !tbaa !5
  %185 = sext i32 %184 to i64
  %186 = sext i32 %.093.lcssa to i64
  %187 = mul nsw i64 %185, %186
  %188 = sext i32 %130 to i64
  %189 = srem i64 %187, %188
  %190 = tail call noundef i32 @_Z7mod_invi(i32 noundef %.092.lcssa)
  %191 = sext i32 %190 to i64
  %192 = mul nsw i64 %189, %191
  %193 = load i32, ptr @p, align 4, !tbaa !5
  %194 = sext i32 %193 to i64
  %195 = srem i64 %192, %194
  %196 = trunc nsw i64 %195 to i32
  store i32 %196, ptr @coeff, align 4, !tbaa !5
  %indvars.iv.next252 = add nuw nsw i64 %indvars.iv251, 1
  %197 = load i32, ptr @n, align 4, !tbaa !5
  %198 = sext i32 %197 to i64
  %.not123.not = icmp slt i64 %indvars.iv251, %198
  br i1 %.not123.not, label %.lr.ph209, label %.critedge129, !llvm.loop !31

.critedge129:                                     ; preds = %._crit_edge204, %._crit_edge185, %74, %.preheader131
  %199 = load i32, ptr @ans, align 4, !tbaa !5
  %200 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.1, i32 noundef %199)
  ret i32 0
}

; Function Attrs: nofree nounwind
declare noundef i32 @__isoc99_scanf(ptr nocapture noundef readonly, ...) local_unnamed_addr #3

; Function Attrs: nofree nounwind
declare noundef i32 @printf(ptr nocapture noundef readonly, ...) local_unnamed_addr #3

attributes #0 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #2 = { mustprogress norecurse uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { nofree nounwind "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"bool", !7, i64 0}
!11 = !{i8 0, i8 2}
!12 = !{}
!13 = distinct !{!13, !14}
!14 = !{!"llvm.loop.mustprogress"}
!15 = distinct !{!15, !14}
!16 = distinct !{!16, !14, !17, !18}
!17 = !{!"llvm.loop.isvectorized", i32 1}
!18 = !{!"llvm.loop.unroll.runtime.disable"}
!19 = distinct !{!19, !14}
!20 = distinct !{!20, !14, !18, !17}
!21 = distinct !{!21, !14}
!22 = distinct !{!22, !14}
!23 = distinct !{!23, !14}
!24 = distinct !{!24, !14}
!25 = distinct !{!25, !14}
!26 = distinct !{!26, !14}
!27 = distinct !{!27, !14}
!28 = distinct !{!28, !14}
!29 = distinct !{!29, !14}
!30 = distinct !{!30, !14}
!31 = distinct !{!31, !14}


; Effective O3 passes: BDCEPass,CorrelatedValuePropagationPass,EarlyCSEPass,GVNPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopInstSimplifyPass,LoopLoadEliminationPass,LoopRotatePass,LoopSimplifyPass,LoopUnrollPass,LoopVectorizePass,ReassociatePass,SCCPPass,SROAPass,SimplifyCFGPass,TailCallElimPass