Cognito Credentials are not authorized to perform Execute api

I am trying to create a role-based access control using AWS Cognito groups. I have the following Role and policy defined to deny the access to resources

CognitoAuthRole:
      Type: AWS::IAM::Role
      Properties:
        Path: /
        AssumeRolePolicyDocument:
          Version: "2012-10-17"
          Statement:
            - Effect: "Allow"
              Principal:
                Federated: "cognito-identity.amazonaws.com"
              Action:
                - "sts:AssumeRoleWithWebIdentity"
              Condition:
                StringEquals:
                  "cognito-identity.amazonaws.com:aud":
                    Ref: CognitoIdentityPool
                "ForAnyValue:StringLike":
                  "cognito-identity.amazonaws.com:amr": authenticated
        Policies:
          - PolicyName: "CognitoAuthorizedPolicy"
            PolicyDocument:
              Version: "2012-10-17"
              Statement:
                - Effect: "Deny"
                  Action: "*"
                  Resource: "*"

And then I created a group called admin incognito user pool and assign a role with a policy to let the user invoke the API as follows

CognitoUserPoolGroupAdmin:
  Type: AWS::Cognito::UserPoolGroup
  Properties:
    UserPoolId:
      Ref: CognitoUserPool
    GroupName: Admin
    Precedence: 0
    RoleArn:
      Fn::GetAtt:
        - AdminRole
        - Arn

AdminRole:
      Type: AWS::IAM::Role
      Properties:
        Path: /
        RoleName: AdminRole
        AssumeRolePolicyDocument:
          Version: "2012-10-17"
          Statement:
            - Effect: "Allow"
              Principal:
                Federated: "cognito-identity.amazonaws.com"
              Action:
                - "sts:AssumeRoleWithWebIdentity"
              Condition:
                StringEquals:
                  "cognito-identity.amazonaws.com:aud":
                    Ref: CognitoIdentityPool
                "ForAnyValue:StringLike":
                  "cognito-identity.amazonaws.com:amr": authenticated
        Policies:
          - PolicyName: CognitoAdminPolicy
            PolicyDocument:
              Version: "2012-10-17"
              Statement:
                - Effect: "Allow"
                  Action:
                    - "execute-api:Invoke"
                  Resource:
                    - arn:aws:execute-api:ap-south-1:****:***/*/GET/user

And then I created a user and added to the group admin and obtained temp credentials and then tried to invoke the API and got following 403 error in postman

"User: arn:aws:sts::******:assumed-role/auth-service-dev-CognitoAuthRole-1JO2U7LKRJRBB/CognitoIdentityCredentials is not authorized to perform: execute-api:Invoke on resource: arn:aws:execute-api:ap-south-1:********2015:****/dev/GET/user with an explicit deny"

This was working perfectly and started causing this error after removing and redeploying the cloud formation stacks.